Kontekstno neovisni jezik

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.

Primjeri

Kanonski primjer kontekstno neovisnog jezika jest ${\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}$, jezik svih nepraznih nizova znakova (simbola) parne duljine, čiju prvu polovicu čine znakovi ${\displaystyle a}$, dok drugu polovicu čine znakovi ${\displaystyle b}$. ${\displaystyle L}$ generira gramatika ${\displaystyle S\to aSb~|~ab}$ te prihvaća potisni automat ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a\},\{a,b,z\},\delta ,q_{0},\{q_{f}\})}$ gdje je funkcija prijelaza ${\displaystyle \delta }$ definirana na sljedeći način:

${\displaystyle \delta (q_{0},a,z)=(q_{0},a)}$
${\displaystyle \delta (q_{0},b,ax)=(q_{1},x)}$
${\displaystyle \delta (q_{1},b,ax)=(q_{1},x)}$
${\displaystyle \delta (q_{1},b,bz)=(q_{f},z)}$

Kontekstno neovisni jezici imaju mnoge primjene u programskim jezicima; na primjer - jezik svih pravilno uparenih zagrada generira gramatika ${\displaystyle S\to SS~|~(S)~|~\lambda }$. Također, većinu aritmetičkih izraza mogu generirati kontekstno neovisne gramatike.

Svojstva zatvorenosti

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 ${\displaystyle L^{*}}$ nad jezikom L
• homeomorfizam φ(L) jezika L
• nadovezivanje (konkatenacija) ${\displaystyle L\circ P}$ jezika L i jezika P
• unija ${\displaystyle L\cup P}$ jezika L i jezika P
• presjek (s regularnim jezikom) ${\displaystyle L\cap D}$ jezika L i jezika D

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