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

Из Википедије, слободне енциклопедије

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

Примери[уреди]

Класичан пример контекстно слободног језика је 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 је регуларан језик, онда су и следећи језици контекстно-слободни:

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

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

Контекстно слободни језици нису затворени за пресек. Ово се може видети ако се узму језици 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). „Context-Free Languages“. Introduction to the Theory of Computation. PWS Publishing. стр. pp-91–122. ISBN 978-0-534-94728-6. 
Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.