Математическая теория формальных языков
Языки Дика и Лукасевича
Определение 7.4.1.
Языком Дика (Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом {a1,b1,a2,b2,...,an,bn}, порождаемый грамматикой
Замечание 7.4.2.
Словами этого языка являются последовательности правильно вложенных скобок n типов (если считать символ ai левой скобкой, а символ bi соответствующей правой скобкой).
Теорема 7.4.3.
Слово w над алфавитом {a,b} выводится в грамматике
тогда и только тогда, когда
и для всех слов
выполняется неравенство
Теорема 7.4.4.
При любом положительном целом n грамматика из определения 7.4.1 является однозначной.
Определение 7.4.5.
Языком Лукасевича (Lukasiewicz language) над n + 1 буквами называется контекстно-свободный язык над алфавитом {a0,a1,...,an}, порождаемый грамматикой
Теорема 7.4.6.
Слово w над алфавитом {a0,a1,...,an} принадлежит языку Лукасевича над n + 1 буквами тогда и только тогда, когда
и для всех слов , кроме x = w, выполняется неравенство
Теорема 7.4.7.
При любом
грамматика из определения 7.4.5 является однозначной.
Упражнение 7.4.8. Принадлежит ли слово aababb языку, порождаемому грамматикой
Упражнение 7.4.9. Принадлежит ли слово cacbcbbacacccaaaacabcaa языку, порождаемому грамматикой
Упражнение 7.4.10. Эквивалентны ли грамматика
и грамматика
Упражнение 7.4.11. Описать язык, порождаемый грамматикой
Упражнение 7.4.12. Описать язык, порождаемый грамматикой
Упражнение 7.4.13. Найти однозначную контекстно-свободную грамматику, порождающую язык .
