Lema o napihovanju

Lema o napihovanju za regularne jezike

Lema o napihovanju za regularne jezike je pripomoček s katerim dokažemo, ali je nek jezik regularen.

Če uporabimo razlago z DKA avtomati: Lema o napihovanju pravi, da za regularne jezike obstaja nek niz w dolžine n, daljši od števila stanj avtomata |Q|.
Potem lahko razdelimo niz na tri dele - w = uvz

u - od začetnega stanja do nekega vmesnega stanja

vⁱ - i-kratna ponovitev nekega cikla okrog vmesnega stanja (če je n > |Q|, cikel gotovo obstaja, i >= 0)

z - niz od vmesnega stanja (po ciklanju), do končenga stanja

Napihovanje imenujemo tisti srednji del, ko se nič ali večkrat zavrtimo v ciklu. Če danega niza iz jezika ni moč razdeliti na zgornji način za nobeno dolžino n, potem ta jezik ni regularen.

Za dokaz regularnosti jezika uporabimo dokazovanje s protislovjem - predpostavimo, da je jezik regularen, potem pa (na vseh delitvah jezika) poskušamo dokazati, da lema o napihovanju ne velja. Če nam to uspe dokazati, smo prišli v protislovje, saj lema velja za vse regularne jezike.

Lema o napihovanju za kontekstno neodvisne gramatike

Ta članek (oz. del besedila) ni popoln, ali pa mu manjka veliko vsebine. Nihče še ni bil dovolj priden, da bi to storil - iščejo se prostovoljci.