Svojstvo napuhavanja

U teoriji formalnih jezika te teoriji izračunljivosti, svojstvo napuhavanja (rjeđe još i lema napuhavanja) kaže da svaki jezik dane klase može biti "napuhan" i pritom još uvijek pripadati danoj klasi. Jezik može biti napuhan ako dovoljno dugi niz znakova jezika se može rastaviti na podnizove, od kojih neki mogu biti ponavljani proizvoljan broj puta u svrhu stvaranja novog, duljeg niza znakova koji je još uvijek u istom jeziku. Stoga, ako vrijedi svojstvo napuhavanja za danu 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.

Dva najvažnija primjera su

• svojstvo napuhavanja za regularne jezike
• svojstvo napuhavanja za kontekstno neovisne jezike.

Ogdenova lema je druga, jača lema napuhavanja za kontekstno neovisne jezike.

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

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