Osobina napuhavanja

U teoriji formalnih jezika te teoriji računanja, osobina napuhavanja ili lema napuhavanja (engl. pumping lemma) kaže da svaki jezik date klase može biti "napuhan" i pritom još uvijek pripadati datoj klasi. Jezik može biti napuhan ako se dovoljno dugi niz znakova jezika može rastaviti na podnizove, od kojih neki mogu biti ponavljani proizvoljan broj puta u svrhu stvaranja novog, dužeg niza znakova koji je još uvijek u istom jeziku. Stoga, ako vrijedi osobina napuhavanja za datu klasu jezika, bilo koji neprazni jezik u klasi će sadržavati beskonačan skup konačnih nizova znakova izgrađenih jednostavnim pravilom koje daje svojstvo napuhavanja. Okosnicu dokaza ovih svojstava obično čine argumenti pobrojavanja kao što je Dirichletov princip kutija.

Dva najvažnija primjera su osobina napuhavanja za regularne jezike i osobina napuhavanja za kontekstno nezavisne jezike. Ogdenova lema je druga, jača lema napuhavanja za kontekstno nezavisne jezike.

Ove se leme mogu koristiti za određivanje ne pripada li neki pojedinačni jezik datoj klasi jezika. Međutim, ne mogu se koristiti za određivanje pripadnosti jezika datoj klasi, budući da zadovoljavanje leme jest nužan, ali ne i dovoljan uslov za pripadnost klasi.

Reference

• (en) Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, str. 115–119.
• (en) Thomas A. Sudkamp (2006). Languages and Machines, Third edition. Adison Wesley. ISBN 0-321-32221-5. Chapter 6: Properties of Regular Languages str. 205–210.
• (en) John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation. Pearson, Addison Wesley. ISBN ISBN 0-321-21029-8.CS1 održavanje: više imena: authors list (link) stranice 126-129, 275-280.

Vanjski linkovi

• http://www.youtube.com/watch?v=sqkcpQw-78A