Kontekstno nezavisni jezik

Iz Wikipedije, slobodne enciklopedije

U formalnoj teoriji jezika, kontekstno slobodni jezik je jezik koji generiše neka kontekstno-slobodna gramatika. Skup svih kontekstno slobodnih jezika je identičan skupu jezika koje prihvataju potisni automati.

Primeri[uredi - уреди | uredi izvor]

Klasičan primer kontekstno slobodnog jezika je , jezik svih nepraznih niski parne dužine, čije ja prva polovina sastavljena od slova , a druga polovina je sastavljena od slova . je generisan gramatikom , a prihvata ga potisni automat gde je definisano na sledeći način:






where je početni simbol steka a predstavlja akciju skidanja sa steka.

Kontekstno slobodni jezici imaju mnoge primene u programskim jezicima; na primer, jezik svih ispravno uparenih zagrada je generisan gramatikom . Takođe, većina aritmetičkih izraza su generisani kontekstno slobodnim gramatikama.


Svojstva zatvorenja[uredi - уреди | uredi izvor]

Kontekstno slobodni jezici su zatvoreni u odnosu na sledeće operacije. To jest, ako su -{L}- i -{P}- kontekstno slobodni jezici, a -{D}- je regularan jezik, onda su i sledeći jezici kontekstno-slobodni:

  • Klinijeva zvezda od -{L}-
  • slika -{φ(L)}- od -{L}- za homomorfizam -{φ}-
  • konkatenacija (dopisivanje) jezika -{L}- i -{P}-
  • unija jezika -{L}- i -{P}-
  • presek (sa regularniim jezikom) jezika -{L}- i -{D}-

Kontekstno slobodni jezici nisu zatvoreni za komplement, presek i razliku.

Nezatvorenost u odnosu na presek[uredi - уреди | uredi izvor]

Kontekstno slobodni jezici nisu zatvoreni za presek. Ovo se može videti ako se uzmu jezici i , koji su oba konetksno slobodna. Njihov presek je , za šta se može pokazati da nije kontekstno slobodan jezik pamping lemom za kontekstno slobodne jezike.

Svojstva odlučivosti[uredi - уреди | uredi izvor]

Sledeći problemi su neodlučivi za proizvoljne kontekstno slobodne gramatike -{A}- i -{B}-:

  • Ekvivalencija: da li je ?
  • da li je  ?
  • da li je  ?
  • da li je  ?

Sledeći problemi su odlučivi za proizvoljne kontekstno slobodne gramatike:

  • da li je ?
  • da li je konačan?
  • Pripadnost: za svaku datu reč , da li je  ? (problem pripadnosti je čak odlučiv u polinomijalnom vremenu - videti -{algoritam CYK}-)

Svojstva kontekst-slobodnih jezika[uredi - уреди | uredi izvor]

Reference[uredi - уреди | uredi izvor]

  • Seymour Ginsburg (1966). The Mathematical Theory of Context-Free Languages. New York, NY, USA: McGraw-Hill, Inc.. 
  • Michael Sipser]] (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Chapter 2: Context-Free Languages, pp.91–122.
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.