Контекст-слободни језик

У формалној теорији језика, контекстно слободни језик је језик који генерише нека контекстно-слободна граматика. Скуп свих контекстно слободних језика је идентичан скупу језика које прихватају потисни аутомати.

Примери

Класичан пример контекстно слободног језика је $L=\{a^n{b}^n:n\ge 1\}$, језик свих непразних ниски парне дужине, чије ја прва половина састављена од слова $a$, а друга половина је састављена од слова $b$. $L$ је генерисан граматиком $S\to aSb|ab$, а прихвата га потисни аутомат $M=(\{q_0,q_1,q_f\},\{a,b\},\{a,z\},\delta ,q_0,\{q_f\})$ где је $\delta$ дефинисано на следећи начин:

$\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$ је почетни симбол стека а $x$ представља акцију скидања са стека.

Контекстно слободни језици имају многе примене у програмским језицима; на пример, језик свих исправно упарених заграда је генерисан граматиком $S\to SS|(S)|\lambda$. Такође, већина аритметичких израза су генерисани контекстно слободним граматикама.

Својства затворења

Контекстно слободни језици су затворени у односу на следеће операције. То јест, ако су -{L}- и -{P}- контекстно слободни језици, а -{D}- је регуларан језик, онда су и следећи језици контекстно-слободни:

• Клинијева звезда $L^{*}$ од -{L}-
• слика -{φ(L)}- од -{L}- за хомоморфизам -{φ}-
• конкатенација (дописивање) $L\circ P$ језика -{L}- и -{P}-
• унија $L\cup P$ језика -{L}- и -{P}-
• пресек (са регуларниим језиком) $L\cap D$ језика -{L}- и -{D}-

Контекстно слободни језици нису затворени за комплемент, пресек и разлику.

Незатвореност у односу на пресек

Контекстно слободни језици нису затворени за пресек. Ово се може видети ако се узму језици $A=\{a^m{b}^n{c}^n\mid m,n\ge 0\}$ и $B=\{a^n{b}^n{c}^m\mid m,n\ge 0\}$, који су оба конетксно слободна. Њихов пресек је $A\cap B=\{a^n{b}^n{c}^n\mid n\ge 0\}$, за шта се може показати да није контекстно слободан језик пампинг лемом за контекстно слободне језике.

Својства одлучивости

Следећи проблеми су неодлучиви за произвољне контекстно слободне граматике -{A}- и -{B}-:

• Еквиваленција: да ли је $L(A)=L(B)$?
• да ли је $L(A)\cap L(B)=\mathrm{\varnothing }$ ?
• да ли је $L(A)={\mathrm{\Sigma }}^{*}$ ?
• да ли је $L(A)\subseteq L(B)$ ?

Следећи проблеми су одлучиви за произвољне контекстно слободне граматике:

• да ли је $L(A)=\mathrm{\varnothing }$?
• да ли је $L(A)$ коначан?
• Припадност: за сваку дату реч $w$, да ли је $w\in L(A)$ ? (проблем припадности је чак одлучив у полиномијалном времену - видети -{алгоритам CYK}-)

Својства контекст-слободних језика

• Језик обратан контекстно слободном језику је контекстно слободан, али његов комплемент не мора да буде.
• Сваки регуларан језик је контекстно слободан јер може да се опише регуларном граматиком.
• Пресек контекстно слободног језика и регуларног језика је увек контекстно слободан.
• Постоје контекстно сензитивни језици који нису контексткно слободни.
• У доказивању да неки језик није контекстно слободан може да се користи пампинг лема за контекстно слободне језике.

Литература

• Шаблон:Cite book
• Шаблон:Cite book