Vidi kôd stranice Svojstvo napuhavanja za regularne jezike

U teoriji [[formalni jezik|formalnih jezika]], '''svojstvo napuhavanja za regularne jezike''' je lema koja iskazuje svojstvo koje svi [[regularni jezik|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''| &ge; ''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''| &le; ''p'', |''y''| &gt; 0 i
:''xy <sup>i</sup> z'' je u ''L'' za svaki cijeli broj ''i'' &ge; 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'' &isin; ''L'' i cijelog broja ''i'' za koje svojstvo napuhavanja ne vrijedi.

Na primjer, koristeći lemu se može dokazati da jezik
''L'' = {''a<sup>n</sup>b<sup>n</sup>'' : ''n'' &ge; 0} nad [[abeceda (računarstvo)|abecedom]] &Sigma; = {''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<sup>p</sup>b<sup>p</sup>''. Očito je taj niz znakova u ''L'', a svojstvo napuhavanja stoga daje rastav niza ''w'' = ''xyz'' pri čemu je |''xy''| &le;  ''p'', |''y''| &ge; 1 i
''xy<sup>i</sup>z'' u L za svaki ''i'' &ge; 0. Budući da su prvih ''p'' znakova svi znakovi ''a'', znamo da je ''xy'' u {''a''*}.  Zbog |''y''| &ge; 1, niz se sastoji od nenultog broja znakova ''a'', i ''xy<sup>2</sup>z'' ima više znakova ''a'' nego znakova ''b'' te stoga nije u ''L'' (uočimo da bilo koja vrijednost za ''i'' &ne; 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.

[[Datoteka:An automat accepting the language a(bc)*d.png]]

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''| &le; ''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<sup>R</sup>v : u,v <math>\in</math> {0,1}<sup>+</sup>}'' (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<sup>R</sup>v'' je duljine od barem 4. Ako je ''u'' duljine 1, tada |''v''| &ge; 2 i uzimamo ''y'' kao prvi znak u  ''v''. Inače uzimamo ''y'' kao prvi znak u ''u'' i uočavamo da ''y<sup>k</sup>'' za ''k'' &ge; 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čni automat|konačnog automata]] ili [[regularni izraz|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''| &ge; ''p'' može biti zapisan u obliku; gdje je ''p'' duljina napuhavanja.
:''uwv'' = ''uxyzv''
pri čemu za podnizove ''x'', ''y'' i ''z'' vrijedi |''xy''| &le; ''p'', |''y''| &gt; 0 i
:''uxy<sup>i</sup>zv'' je u ''L'' za svaki cijeli broj ''i'' &ge; 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 ==
* {{cite book  | author = [[Michael Sipser]]  | year = 1997  | title = Introduction to the Theory of Computation  | publisher = PWS Publishing  | id = {{ISBN|0-534-94728-X}}}}
* {{cite book  | author = Siniša Srbljić  | title = Jezični procesori 1  | publisher = Element  | year = 2003  | id = {{ISBN|953-197-129-3}}}}

[[Kategorija:Formalni jezici]]

[[de:Pumping-Lemma#Reguläre Sprachen]]