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

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

ПримериУреди

Класичан пример контекстно слободног језика је  , језик свих непразних ниски парне дужине, чије ја прва половина састављена од слова  , а друга половина је састављена од слова  .   је генерисан граматиком  , а прихвата га потисни аутомат   где је   дефинисано на следећи начин:

 
 
 
 
 

 
where   је почетни симбол стека а   представља акцију скидања са стека.

Контекстно слободни језици имају многе примене у програмским језицима; на пример, језик свих исправно упарених заграда је генерисан граматиком  . Такође, већина аритметичких израза су генерисани контекстно слободним граматикама.


Својства затворењаУреди

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

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

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

Контекстно слободни језици нису затворени за пресек. Ово се може видети ако се узму језици   и  , који су оба конетксно слободна. Њихов пресек је  , за шта се може показати да није контекстно слободан језик пампинг лемом за контекстно слободне језике.

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

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

  • Еквиваленција: да ли је  ?
  • да ли је   ?
  • да ли је   ?
  • да ли је   ?

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

  • да ли је  ?
  • да ли је   коначан?
  • Припадност: за сваку дату реч  , да ли је   ? (проблем припадности је чак одлучив у полиномијалном времену - видети алгоритам CYK)

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

ЛитератураУреди

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
% (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
% Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
% Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.