Svojstvo napuhavanja za regularne jezike

U teoriji formalnih jezika, svojstvo napuhavanja za regularne jezike je lema koja iskazuje svojstvo koje svi regularni jezici moraju zadovoljavati. Primarna uporaba leme jest u svrhu dokazivanja neregularnosti jezika.

Formalni iskaz

Ako je jezik L regularan, tada postoji broj p > 0 takav da za svaki niz znakova w u L za koji je |w| ≥ p može biti zapisan u sljedećem obliku, pri čemu je p duljina napuhavanja:

w = xyz

s podnizovima x, y i z takvim da |xy| ≤ p, |y| > 0 i

xy ⁱ z je u L za svaki cijeli broj i ≥ 0.

Uporaba leme

Prilikom korištenja leme za dokazivanje neregularnosti jezika, obično se koristi dokaz kontradikcijom. Ako pretpostavimo da je jezik L regularan, tada svojstvo napuhavanja mora biti zadovoljeno za sve nizove znakova u L. Pokazivanjem postojanja niza znakova za kojeg svojstvo napuhavanja ne vrijedi, ujedno pokazujemo i netočnost početne pretpostavke. Na taj se način dokaz svodi na traženje niza znakova w ∈ L i cijelog broja i za koje svojstvo napuhavanja ne vrijedi.

Na primjer, koristeći lemu se može dokazati da jezik L = {aⁿbⁿ : n ≥ 0} nad abecedom Σ = {a, b} nije regularan. Neka su w, x, y, z, p, i i onako kako je iskazano u svojstvu napuhavanja za regularne jezike. Neka je w = a^pb^p. Očito je taj niz znakova u L, a svojstvo napuhavanja stoga daje rastav niza w = xyz pri čemu je |xy| ≤ p, |y| ≥ 1 i xyⁱz u L za svaki i ≥ 0. Budući da su prvih p znakova svi znakovi a, znamo da je xy u {a*}. Zbog |y| ≥ 1, niz se sastoji od nenultog broja znakova a, i xy²z ima više znakova a nego znakova b te stoga nije u L (uočimo da bilo koja vrijednost za i ≠ 1 daje protuslovlje). Sad smo došli do protuslovlja (kontradikcije) pošto, u ovom slučaju, svojstvo napuhavanja nije zadovoljeno. Stoga je pretpostavka o regularnosti jezika L netočna. L nije regularni jezik.

Dokaz da jezik uparenih (tj. odgovarajuće ugniježđenih) zagrada nije regularan slijedi istu liniju zaključivanja. Za dani p postoji niz uparenih zagrada koji počinje s više od p lijevih otvorenih zagrada, tako da će y sadržavati samo lijeve otvorene zagrade. Ponavljanjem niza y možemo izgraditi niz znakova koji ne sadrži jednak broj lijevih i desnih zagrada, pa tako njihov broj ne može biti balansiran.

Dokaz svojstva napuhavanja

Ideja dokaza koristi činjenicu da za svaki regularni jezik postoji konačni automat (KA) koji prihvaća jezik. Ako je regularni jezik konačan, tada slijedi da je svojstvo napuhavanja trivijalno istinito, pošto ne postoje nizovi znakova u jeziku veći od duljine napuhavanja.

Ako je regularni jezik konačan, tada mora postojati neki minimalni KA koji prihvaća jezik. Broj stanja u ovom KA je izbrojen, te je potom taj broj korišten kao duljina napuhavanja p. Ako je duljina niza znakova veća od p, tada mora postojati barem jedno stanje koje se ponavlja (koje ćemo nazvati stanje S). Prijelazi koji vode stroj iz stanja S natrag u stanje S odgovaraju nekom nizu znakova. Taj se niz znakova u formalnom iskazu leme zove y, a pošto će stroj prihvatiti niz znakova bez y dijela, ili niz znakova y može biti proizvoljno ponavljan, uvjeti leme su zadovoljeni.

Ovo postaje znatno razumljivije uz konkretan primjer. Sljedeća slika prikazuje dijagram stanja KA.

KA prihvaća niz znakova abcbcd. Budući da je ovaj niz dulji od broja stanja, postoje stanja koja se ponavljaju. U ovom primjeru, ponavljana stanja su stanja q1 i q2. Budući da podniz bcbc niza znakova abcbcd vodi stroj kroz slijed prijelaza koji započinju stanjem q1 i završavaju stanjem q1, dio niza znakova može biti ponavljan pri čemu bi KA dalje prihvaćao dani niz znakova abcbcbcbcd, baš kao i kad bi dio niza znakova bio maknut pri čemu bi KA i dalje prihvaćao niz znakova ad. U terminima formalnog iskaza svojstva napuhavanja, niz znakova abcbcd je razbijen u x dio a, y dio bc te z dio bcd. (Uočimo da je mogao biti razbijen i na druge načine, poput x dijela a, y dijela bcbc, te z dijela d, pri čemu bi svi uvjeti bili zadovoljeni osim |xy| ≤ p)

Svojstvo nije dovoljno

Uočimo da svojstvo napuhavanja ne daje dovoljne uvjete da bi jezik bio regularan. To jest, neki neregularni jezici također zadovoljavaju svojstvo napuhavanja. Ako neki jezik L ne zadovoljava svojstvo napuhavanja, tada L nije regularni jezik. Ako neki jezik L zadovoljava svojstvo napuhavanja, L može biti regularan. Na primjer, jezik {uu^Rv : u,v $\in$ {0,1}⁺} (nizovi znakova nad abecedom {0,1} koji se sastoje od nepraznih palindroma parne duljine nakon kojih slijedi neprazni niz znakova) nije regularan, ali može svejedno biti "napuhan" sa p = 4: Pretpostavimo w=uu^Rv je duljine od barem 4. Ako je u duljine 1, tada |v| ≥ 2 i uzimamo y kao prvi znak u v. Inače uzimamo y kao prvi znak u u i uočavamo da y^k za k ≥ 2 započinje s nepraznim palindromom yy. Za praktični test koji točno karakterizira regularne jezike, pogledati Myhill-Nerode teorem. Tipična metoda dokazivanja regularnosti jezika jest konstrukcija konačnog automata ili regularnog izraza za jezik.

Općenita verzija svojstva napuhavanja za regularne jezike

Ako je jezik L regularan, tada postoji broj p > 0 takav da se svaki niz znakova uwv u L za koji je |w| ≥ p može biti zapisan u obliku; gdje je p duljina napuhavanja.

uwv = uxyzv

pri čemu za podnizove x, y i z vrijedi |xy| ≤ p, |y| > 0 i

uxyⁱzv je u L za svaki cijeli broj i ≥ 0.

Ova se verzija svojstva napuhavanja može koristiti prilikom dokaza neregularnosti mnogo šire klase jezika, pošto postavlja strože zahtjeve nad jezikom.

Vidjeti također

• Svojstvo napuhavanja

Izvori

• Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X
• Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3