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 Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, str. 115–119. Chapter 6: Properties of Regular Languages str. 205–210. stranice 126-129, 275-280. Vanjski linkovi http://www.youtube.com/watch?v=sqkcpQw-78A
Kategorija:Formalni jezici Kategorija:Leme