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

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

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

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

• Формальные грамматики
• Иерархия Хомского формальных грамматик
• Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
• Правоконтекстные грамматики, эквивалентность автоматам
• Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
• Удаление бесполезных символов из грамматики
• Удаление eps-правил из грамматики
• Удаление цепных правил из грамматики
• Удаление длинных правил из грамматики
• Нормальная форма Хомского
• Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
• Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
• Алгоритм Эрли
• Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
• Устранение левой рекурсии
• Приведение грамматики к ослабленной нормальной форме Грейбах
• Лемма о разрастании для КС-грамматик
• Автоматы с магазинной памятью
• МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
• Совпадение множества языков МП-автоматов и контекстно-свободных языков
• Детерминированные автоматы с магазинной памятью
• Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
• Нормальная форма ДМП-автомата

Теория вычислимости

• [[Диагональный метод. Невозможность одновременного существования универсальной функции и всюду определенности всех элементов семейства вычислимых функций]]