Языки Дика и Лукасевича

Определение 7.4.1. Языком Дика (Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом {a₁,b₁,a₂,b₂,...,a_n,b_n}, порождаемый грамматикой

Замечание 7.4.2. Словами этого языка являются последовательности правильно вложенных скобок n типов (если считать символ a_i левой скобкой, а символ b_i соответствующей правой скобкой).

Теорема 7.4.3. Слово w над алфавитом {a,b} выводится в грамматике

тогда и только тогда, когда

и для всех слов выполняется неравенство

Теорема 7.4.4. При любом положительном целом n грамматика из определения 7.4.1 является однозначной.

Определение 7.4.5. Языком Лукасевича (Lukasiewicz language) над n + 1 буквами называется контекстно-свободный язык над алфавитом {a₀,a₁,...,a_n}, порождаемый грамматикой

Теорема 7.4.6. Слово w над алфавитом {a₀,a₁,...,a_n} принадлежит языку Лукасевича над n + 1 буквами тогда и только тогда, когда

и для всех слов , кроме x = w, выполняется неравенство

Теорема 7.4.7. При любом грамматика из определения 7.4.5 является однозначной.

Основная цель этой лекции - доказать, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского (раздел 8.3). Этот факт используется дальше в доказательствах многих теорем о контекстно-свободных языках. Два вспомогательных результата, на которые опирается приведение грамматик к нормальной форме Хомского, выделены в отдельные разделы в начале лекции.

В конце лекции доказывается, что каждую контекстно-свободную грамматику можно также привести к нормальной форме Грейбах.