Otvori glavni izbornik

Kontekstno neovisni jezik (rjeđe još i kontekstno slobodni jezik ili jezik neovisan o sadržaju, te još i bezokolinski jezik[1]) je formalni jezik koji je element skupa jezika kojeg definiraju kontekstno neovisne gramatike. Skup kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju potisni automati.

PrimjeriUredi

Kanonski primjer kontekstno neovisnog jezika jest  , jezik svih nepraznih nizova znakova (simbola) parne duljine, čiju prvu polovicu čine znakovi  , dok drugu polovicu čine znakovi  .   generira gramatika   te prihvaća potisni automat   gdje je funkcija prijelaza   definirana na sljedeći način:

 
 
 
 

Kontekstno neovisni jezici imaju mnoge primjene u programskim jezicima; na primjer - jezik svih pravilno uparenih zagrada generira gramatika  . Također, većinu aritmetičkih izraza mogu generirati kontekstno neovisne gramatike.

Svojstva zatvorenostiUredi

Kontekstno neovisni jezici su zatvoreni nad sljedećim operacijama. To jest, ako su L i P kontekstno neovisni jezici i D je regularni jezik, sljedeći jezici su također kontekstno neovisni:

  • Kleeneov operator   nad jezikom L
  • homeomorfizam φ(L) jezika L
  • nadovezivanje (konkatenacija)   jezika L i jezika P
  • unija   jezika L i jezika P
  • presjek (sa regularnim jezikom)   jezika L i jezika D

Kontekstno neovisni jezici nisu zatvoreni nad operacijama komplementa, presjeka i razlike.

IzvoriUredi

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 234
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.