Kontekstno nezavisni jezik

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
Klasičan primer kontekstno slobodnog jezika je L = \{a^nb^n:n\geq1\}, jezik svih nepraznih niski parne dužine, čije ja prva polovina sastavljena od slova a, a druga polovina je sastavljena od slova b. L je generisan gramatikom S\to aSb ~|~ ab, a prihvata ga potisni automat M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, \{q_f\}) gde je \delta definisano na sledeći način:


\delta(q_0, a, z) = (q_0, a)
\delta(q_0, a, a) = (q_0, a)
\delta(q_0, b, a) = (q_1, x)
\delta(q_1, b, a) = (q_1, x)
\delta(q_1, \lambda, z) = (q_f, z)

\delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})
where z je početni simbol steka a x predstavlja akciju skidanja sa steka.


Kontekstno slobodni jezici imaju mnoge primene u programskim jezicima; na primer, jezik svih ispravno uparenih zagrada je generisan gramatikom S\to SS ~|~ (S) ~|~ \lambda. Takođe, većina aritmetičkih izraza su generisani kontekstno slobodnim gramatikama.

## Svojstva zatvorenja
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 L^* od *-{L}-*
* slika -{φ(L)}- od *-{L}-* za homomorfizam -{φ}- 
* konkatenacija (dopisivanje) L \circ P jezika *-{L}-* i *-{P}-*
* unija L \cup P jezika *-{L}-* i *-{P}-*
* presek (sa regularniim jezikom) L \cap D jezika *-{L}-* i *-{D}-*

Kontekstno slobodni jezici nisu zatvoreni za komplement, presek i razliku.

### Nezatvorenost u odnosu na presek
Kontekstno slobodni jezici nisu zatvoreni za presek. Ovo se može videti ako se uzmu jezici A = \{a^m b^n c^n \mid m, n \geq 0 \} i B = \{a^n b^n c^m \mid m,n \geq 0\}, koji su oba konetksno slobodna. Njihov presek je A \cap B = \{ a^n b^n c^n \mid n \geq 0\}, za šta se može pokazati da nije kontekstno slobodan jezik pamping lemom za kontekstno slobodne jezike.

## Svojstva odlučivosti
Sledeći problemi su neodlučivi za proizvoljne kontekstno slobodne gramatike -{A}- i -{B}-:
* Ekvivalencija: da li je L(A)=L(B)?
* da li je L(A) \cap L(B) = \emptyset  ?
* da li je L(A)=\Sigma^* ?
* da li je L(A) \subseteq L(B) ?

Sledeći problemi su odlučivi za proizvoljne kontekstno slobodne gramatike:
* da li je L(A)=\emptyset?
* da li je L(A) konačan?
* Pripadnost: za svaku datu reč w, da li je w \in L(A) ? (problem pripadnosti je čak odlučiv u polinomijalnom vremenu - videti -{algoritam CYK}-)

## Svojstva kontekst-slobodnih jezika
* Jezik obratan kontekstno slobodnom jeziku je kontekstno slobodan, ali njegov komplement ne mora da bude.
* Svaki regularan jezik je kontekstno slobodan jer može da se opiše regularnom gramatikom. 
* Presek kontekstno slobodnog jezika i regularnog jezika je uvek kontekstno slobodan. 
* Postoje kontekstno senzitivni jezici koji nisu kontekstkno slobodni.
* U dokazivanju da neki jezik nije kontekstno slobodan može da se koristi pamping lema za kontekstno slobodne jezike.

## Reference
* 
*  Chapter 2: Context-Free Languages, pp.91–122.