Kontekstno nezavisni jezik

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

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

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

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

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

Reference uredi

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.