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

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

Примери

Класичан пример контекстно слободног језика је $L = \{a^nb^n:n\geq1\}$, језик свих непразних ниски парне дужине, чије ја прва половина састављена од слова $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{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})$
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 \geq 0 \}$ и $B = \{a^n b^n c^m \mid m,n \geq 0\}$, који су оба конетксно слободна. Њихов пресек је $A \cap B = \{ a^n b^n c^n \mid n \geq 0\}$, за шта се може показати да није контекстно слободан језик пампинг лемом за контекстно слободне језике.

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

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

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

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

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

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

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

Литература

• 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.