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

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

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

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

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

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

• Разрешимые (рекурсивные) языки
• Перечислимые языки
• Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
• Разрешимость перечислимого и коперечислимого языка
• Вычислимые функции
• Диагональный метод
• Невозможность одновременного существования универсальной функции и всюду определенности всех элементов семейства вычислимых функций
• Характеристика перечислимых множеств через вычислимые функции
• Свойства перечислимых языков. Теорема Успенского-Райса
• Главные нумерации
• Неотделимые множества
• Иммунные и простые множества
• Теорема о рекурсии
• m-сводимость
• Примеры неразрешимых задач: проблема соответствий Поста
• Примеры неразрешимых задач: однозначность грамматики
• Примеры неразрешимых задач: задача о замощении
• Примеры неразрешимых задач: задача о выводе в полусистеме Туэ
• Стековые машины, эквивалентность двухстековой машины МТ
• Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
• Линейный клеточный автомат, эквивалентность МТ
• Возможность порождения формальной грамматикой произвольного перечислимого языка
• Теорема Райса-Шапиро