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

Лекция 1

• Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов
• Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини
• Регулярные языки: два определения и их эквивалентность
• Детерминированные конечные автоматы
• Недетерминированные конечные автоматы
• Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Лекция 2

• Автоматы с eps-переходами. Eps-замыкание
• Теорема Клини (совпадение классов автоматных и регулярных языков
• Эквивалентность состояний ДКА
• Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
• Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
• Замкнутость регулярных языков относительно различных операций
• Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)

Лекция 3

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

Лекция 4

• Формальные грамматики
• Иерархия Хомского формальных грамматик
• Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
• Правоконтекстные грамматики, эквивалентность автоматам
• Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
• Удаление бесполезных символов из грамматики
• Удаление eps-правил из грамматики
• Удаление цепных правил из грамматики
• Удаление длинных правил из грамматики
• Нормальная форма Хомского