Svojstvo napuhavanja
Sa Wikipedije, slobodne enciklopedije
U teoriji formalnih jezika te teoriji računanja, svojstvo napuhavanja kaže da svaki jezik date klase može biti "napuhan" i pritom još uvijek pripadati datoj klasi. Jezik može biti napuhan ukoliko 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, ukoliko vrijedi svojstvo 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.
Dva najvažnija primjera su svojstvo napuhavanja za regularne jezike i svojstvo 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.
[uredi] Reference
- Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; ISBN 0-534-94728-X
