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^n{b}^n:n\ge 1\}$, 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{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}_1,\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d},\mathrm{p}\mathrm{o}\mathrm{p})=({\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}}_2,\mathrm{p}\mathrm{u}\mathrm{s}\mathrm{h})$
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\ge 0\}$ i $B=\{a^n{b}^n{c}^m\mid m,n\ge 0\}$, koji su oba konetksno slobodna. Njihov presek je $A\cap B=\{a^n{b}^n{c}^n\mid n\ge 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)=\mathrm{\varnothing }$ ?
• da li je $L(A)={\mathrm{\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)=\mathrm{\varnothing }$?
• 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

• Šablon:Cite book
• Šablon:Cite book Chapter 2: Context-Free Languages, pp.91–122.