Теория формальных языков

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Автоматы и регулярные языки

Регулярные языки и ДКА

• Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
• Регулярные языки: два определения и их эквивалентность, регулярные выражения
• Детерминированные конечные автоматы
• Прямое произведение ДКА
• Простой сопоставитель регулярных выражений [math] \star [/math]

НКА

• Недетерминированные конечные автоматы
• Построение по НКА эквивалентного ДКА, алгоритм Томпсона
• Автоматы с eps-переходами. Eps-замыкание
• Теорема Клини (совпадение классов автоматных и регулярных языков)
• Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

Минимизация ДКА

• Эквивалентность состояний ДКА
• Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
• Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
• Алгоритм Бржозовского[math] ^\star [/math]

Свойства конечных автоматов

• Доказательство нерегулярности языков: лемма о разрастании
• Интерпретация булевых формул с кванторами как игр для двух игроков
• Решение уравнений в регулярных выражениях
• Замкнутость регулярных языков относительно различных операций
• Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
• Контексты и синтаксические моноиды
• Булевые формулы с кванторами как игры для двух игроков

Другие автоматы

• Локальные автоматы[math] ^\star [/math]
• Двусторонний детерминированный конечный автомат[math] ^\star [/math]
• Квантовые конечные автоматы[math] ^\star [/math]
• Автоматы Мура и Мили[math] ^\star [/math]
• Автоматы в современном мире[math] ^\star [/math]

Контекстно-свободные грамматики

Базовые понятия о грамматиках

• Формальные грамматики
• Иерархия Хомского формальных грамматик
• Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
• Правоконтекстные грамматики, эквивалентность автоматам
• Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
• Замкнутость КС-языков относительно различных операций
• Регулярная аппроксимация КС-языков[math] ^\star [/math]

Нормальные формы КС-грамматик

• Удаление бесполезных символов из грамматики
• Удаление длинных правил из грамматики
• Удаление eps-правил из грамматики
• Удаление цепных правил из грамматики
• Нормальная форма Хомского
• Устранение левой рекурсии
• Приведение грамматики к ослабленной нормальной форме Грейбах
• Нормальная форма Куроды[math] ^\star [/math]

Алгоритмы разбора

• Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
• Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
• Алгоритм Эрли
• Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики

Опровержение контекстно-свободности языка

• Лемма о разрастании для КС-грамматик
• Лемма Огдена
• Существенно неоднозначные языки
• Теорема Парика[math] ^\star [/math]

МП-автоматы

• Автоматы с магазинной памятью
• МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
• Совпадение множества языков МП-автоматов и контекстно-свободных языков
• Детерминированные автоматы с магазинной памятью
• Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
• Нормальная форма ДМП-автомата[math] ^\star [/math]
• Эквивалентность ДМП-автоматов[math] ^\star [/math]
• Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
• ДМП-автоматы и неоднозначность