У формалној теорији језика, контекстно слободни језик је језик који генерише нека контекстно-слободна граматика. Скуп свих контекстно слободних језика је идентичан скупу језика које прихватају потисни аутомати.
Примери Класичан пример контекстно слободног језика је , језик свих непразних ниски парне дужине, чије ја прва половина састављена од слова , а друга половина је састављена од слова . је генерисан граматиком , а прихвата га потисни аутомат где је дефинисано на следећи начин:
where је почетни симбол стека а представља акцију скидања са стека.
Контекстно слободни језици имају многе примене у програмским језицима; на пример, језик свих исправно упарених заграда је генерисан граматиком . Такође, већина аритметичких израза су генерисани контекстно слободним граматикама.
Својства затворења Контекстно слободни језици су затворени у односу на следеће операције. То јест, ако су -{L}- и -{P}- контекстно слободни језици, а -{D}- је регуларан језик, онда су и следећи језици контекстно-слободни:
Клинијева звезда од -{L}- слика -{φ(L)}- од -{L}- за хомоморфизам -{φ}- конкатенација (дописивање) језика -{L}- и -{P}- унија језика -{L}- и -{P}- пресек (са регуларниим језиком) језика -{L}- и -{D}-
Контекстно слободни језици нису затворени за комплемент, пресек и разлику.
Незатвореност у односу на пресек Контекстно слободни језици нису затворени за пресек. Ово се може видети ако се узму језици и , који су оба конетксно слободна. Њихов пресек је , за шта се може показати да није контекстно слободан језик пампинг лемом за контекстно слободне језике.
Својства одлучивости Следећи проблеми су неодлучиви за произвољне контекстно слободне граматике -{A}- и -{B}-: Еквиваленција: да ли је ? да ли је ? да ли је ? да ли је ?
Следећи проблеми су одлучиви за произвољне контекстно слободне граматике: да ли је ? да ли је коначан? Припадност: за сваку дату реч , да ли је ? (проблем припадности је чак одлучив у полиномијалном времену - видети -{алгоритам CYK}-)
Својства контекст-слободних језика Језик обратан контекстно слободном језику је контекстно слободан, али његов комплемент не мора да буде. Сваки регуларан језик је контекстно слободан јер може да се опише регуларном граматиком. Пресек контекстно слободног језика и регуларног језика је увек контекстно слободан. Постоје контекстно сензитивни језици који нису контексткно слободни. У доказивању да неки језик није контекстно слободан може да се користи пампинг лема за контекстно слободне језике.
Литература
Категорија:Формални језици