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

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

Примери

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Seymour Ginsburg (1966). The Mathematical Theory of Context-Free Languages. New York, NY, USA: McGraw-Hill, Inc.
• Michael Sipser (1997). „Context-Free Languages”. Introduction to the Theory of Computation. PWS Publishing. стр. pp—91—122. ISBN 978-0-534-94728-6.