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).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. 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 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[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 Provjerite vrijednost parametra |isbn= (pomoć).  stranice 126-129, 275-280.

Vanjski linkovi[uredi | uredi izvor]