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 $L = \{a^nb^n:n\geq1\}$, jezik svih nepraznih nizova znakova (simbola) parne dužine, čiju prvu polovicu čine znakovi $a$, dok drugu polovicu čine znakovi $b$. $L$ generiše gramatika $S\to aSb ~|~ ab$ te prihvata potisni automat $M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\})$ gdje je funkcija prijelaza $\delta$ definisana na sljedeći način:

$\delta(q_0, a, z) = (q_0, a)$
$\delta(q_0, b, ax) = (q_1, x)$
$\delta(q_1, b, ax) = (q_1, x)$
$\delta(q_1, b, bz) = (q_f, z)$

Kontekstno nezavisni jezici imaju mnoge primjene u programskim jezicima; na primjer - jezik svih pravilno uparenih zagrada generiše gramatika $S\to SS ~|~ (S) ~|~ \lambda$. 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 $L^*$ nad jezikom L
• homeomorfizam φ(L) jezika L
• nadovezivanje (konkatenacija) $L \circ P$ jezika L i jezika P
• unija $L \cup P$ jezika L i jezika P
• presjek (sa regularnim jezikom) $L \cap D$ jezika L i jezika D

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

Reference

• Michael Sipser - Introduction to the Theory of Computation, PWS Publishing, 1997; ISBN 0-534-94728-X