Kontekstno nezavisni jezik

Kontekstno nezavisni jezik (rjeđe još i kontekstno slobodni jezik) je formalni jezik koji je element skupa jezika kojeg definišu kontekstno nezavisne gramatike. Skup kontekstno nezavisnih jezika je identičan skupu jezika koje prihvataju potisni automati.

 Primjeri 
Kanonski primjer kontekstno nezavisnog jezika jest , jezik svih nepraznih nizova znakova (simbola) parne dužine, čiju prvu polovicu čine znakovi , dok drugu polovicu čine znakovi .  generiše gramatika  te prihvata potisni automat  gdje je funkcija prijelaza  definisana na sljedeći način:

Kontekstno nezavisni jezici imaju mnoge primjene u programskim jezicima; na primjer - jezik svih pravilno uparenih zagrada generiše gramatika . Također, većinu aritmetičkih izraza mogu generisati kontekstno nezavisne gramatike.

 Svojstva zatvorenosti 

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

 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 nezavisni jezici nisu zatvoreni nad operacijama komplementa, presjeka i razlike.

 Također pogledajte 
 Parser

 Reference 

 Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; 

Kategorija:Formalni jezici