Prijeđi na sadržaj

Kontekstno nezavisni jezik

Izvor: Wikipedija

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 kod]

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 kod]

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 kod]

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 kod]

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 kod]

Reference

[uredi | uredi kod]
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.