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 ${\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}$, jezik svih nepraznih niski parne dužine, čije ja prva polovina sastavljena od slova ${\displaystyle a}$, a druga polovina je sastavljena od slova ${\displaystyle b}$. ${\displaystyle L}$ je generisan gramatikom ${\displaystyle S\to aSb~|~ab}$, a prihvata ga potisni automat ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},\{q_{f}\})}$ gde je ${\displaystyle \delta }$ definisano na sledeći način:

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

${\displaystyle \delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )}$
where ${\displaystyle z}$ je početni simbol steka a ${\displaystyle 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 ${\displaystyle 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 i kontekstno slobodni jezici, a je regularan jezik, onda su i sledeći jezici kontekstno-slobodni:

• Klinijeva zvezda ${\displaystyle L^{*}}$ od
• slika od za homomorfizam
• konkatenacija (dopisivanje) ${\displaystyle L\circ P}$ jezika i
• unija ${\displaystyle L\cup P}$ jezika i
• presek (sa regularniim jezikom) ${\displaystyle L\cap D}$ jezika i

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 ${\displaystyle A=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}}$ i ${\displaystyle B=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}}$, koji su oba konetksno slobodna. Njihov presek je ${\displaystyle 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 i :

• Ekvivalencija: da li je ${\displaystyle L(A)=L(B)}$?
• da li je ${\displaystyle L(A)\cap L(B)=\emptyset }$ ?
• da li je ${\displaystyle L(A)=\Sigma ^{*}}$ ?
• da li je ${\displaystyle L(A)\subseteq L(B)}$ ?

Sledeći problemi su odlučivi za proizvoljne kontekstno slobodne gramatike:

• da li je ${\displaystyle L(A)=\emptyset }$?
• da li je ${\displaystyle L(A)}$ konačan?
• Pripadnost: za svaku datu reč ${\displaystyle w}$, da li je ${\displaystyle w\in L(A)}$ ? (problem pripadnosti je čak odlučiv u polinomijalnom vremenu - videti )

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

• Seymour Ginsburg (1966). The Mathematical Theory of Context-Free Languages. New York, NY, USA: McGraw-Hill, Inc..
• Michael Sipser]] (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Chapter 2: Context-Free Languages, pp.91–122.

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.