Osobina napuhavanja

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

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 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 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[uredi | uredi izvor]

  • (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. stranice 126-129, 275-280.

Vanjski linkovi[uredi | uredi izvor]