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

Символом [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]

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

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

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

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

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

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

МП-автоматы

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

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

Разрешимые и перечислимые языки

• Разрешимые (рекурсивные) языки
• Перечислимые языки
• Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
• Вычислимые функции
• Вычислимые числа
• Универсальная функция и главные нумерации
• Свойства перечислимых языков. Теорема Успенского-Райса
• Неотделимые множества
• Иммунные и простые множества
• Теорема о рекурсии
• Квайны[math] ^\star [/math]
• Busy beaver
• Колмогоровская сложность[math] ^\star [/math]

Вычислительные формализмы

• Машина Тьюринга
• Лямбда-исчисление[math] ^\star [/math]
• Примитивно рекурсивные функции[math] ^\star [/math]
• Частично рекурсивные функции[math] ^\star [/math]
• Стековые машины, эквивалентность двухстековой машины МТ
• Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
• Линейный клеточный автомат, эквивалентность МТ
• Возможность порождения формальной грамматикой произвольного перечислимого языка
• Линейный ограниченный автомат
• Сверхтьюринговые вычисления (гипервычисления)[math] ^\star [/math]
• Тьюринг-полнота[math] ^\star [/math]

Примеры неразрешимых задач

• m-сводимость
• Проблема соответствий Поста
• Однозначность КС-грамматики
• Эквивалентность КС-грамматик
• Пустота пересечения КС-грамматик
• Задача о замощении полимино
• Задача о выводе в полусистеме Туэ
• Неразрешимость исчисления предикатов первого порядка
• Неразрешимость проблемы существования решения диофантова уравнения в целых числах
• Игра «Жизнь»[math]^\star[/math]
• Неразрешимость игры Braid[math]^\star[/math]
• Теорема Райса-Шапиро