Учебник Теория автоматов и формальных языков для начинающих

Программа курса

1. 1 Зачем нужна теория вычислений

   1. Что компьютер может и чего не может

      Зачем нужна теория вычислений: фундамент CS, пределы вычислимости, абстрактные модели и почему некоторые задачи неразрешимы в принципе.

   2. Алфавиты, строки и языки

      Формальные определения: алфавит, строка, пустое слово, конкатенация, степень и замыкание Клини, язык как множество строк над алфавитом.

   3. Иерархия Хомского: карта курса

      Четыре типа грамматик и языков по Хомскому: регулярные, контекстно-свободные, контекстно-зависимые, рекурсивно-перечислимые — и какие машины им соответствуют.

2. 2 Конечные автоматы

   1. Детерминированный конечный автомат (ДКА)

      Формальное определение ДКА: пятёрка (Q, Σ, δ, q0, F), диаграмма состояний, таблица переходов, принятие строки и язык автомата.

   2. Недетерминированный автомат (НКА)

      НКА: несколько переходов по одному символу, принятие по существованию принимающего пути, почему недетерминизм удобен для построения автоматов.

   3. ε-переходы и НКА-ε

      ε-переходы в недетерминированных автоматах: переход без чтения символа, ε-замыкание, зачем они нужны для объединения и конкатенации автоматов.

3. 3 Эквивалентность и регулярные языки

   1. Детерминизация: построение подмножеств

      Эквивалентность ДКА и НКА: алгоритм построения подмножеств (subset construction), состояния-множества, экспоненциальный взрыв в худшем случае.

   2. Теорема Клини: регулярки = автоматы

      Теорема Клини: класс языков конечных автоматов совпадает с классом регулярных выражений. Операции регулярок и связь с курсом regex.

   3. Замкнутость регулярных языков

      Регулярные языки замкнуты относительно объединения, конкатенации, звезды, дополнения и пересечения. Конструкция дополнения и произведения автоматов.

   4. Лемма о накачке для регулярных языков

      Лемма о накачке (pumping lemma): инструмент доказательства не-регулярности языка. Формулировка, интуиция через повтор состояний, доказательство для a^n b^n.

4. 4 Минимизация и границы регулярных языков

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

      Минимизация детерминированного автомата: эквивалентные состояния, алгоритм разбиения на классы, единственность минимального ДКА.

   2. Что регулярные языки НЕ могут

      Границы регулярных языков: вложенные скобки, a^n b^n, палиндромы, почему конечной памяти недостаточно и зачем нужен стек.

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

   1. КС-грамматики: правила и вывод

      Контекстно-свободные грамматики: нетерминалы и терминалы, продукции A → γ, вывод строк, связь с BNF и синтаксисом языков программирования.

   2. Деревья разбора и вывод

      Дерево разбора КС-грамматики: структура вывода, левый и правый вывод, как дерево отражает синтаксис выражения и связь с парсерами.

   3. Неоднозначность грамматик

      Неоднозначные КС-грамматики: несколько деревьев разбора для одной строки, классический пример выражений, устранение неоднозначности приоритетом.

   4. Магазинные автоматы (PDA)

      Магазинный (pushdown) автомат: конечный автомат со стеком, переходы с операциями над стеком, распознавание КС-языков, пример a^n b^n.

6. 6 Свойства контекстно-свободных языков

   1. Лемма о накачке для КС-языков

      Лемма о накачке для контекстно-свободных языков: накачка двух участков uv^i wx^i y, доказательство не-КС для a^n b^n c^n.

   2. Нормальная форма Хомского

      Нормальная форма Хомского (CNF): правила A → BC и A → a, зачем приводить грамматику к ней, связь с алгоритмом CYK-разбора.

   3. Границы КС-языков и замкнутость

      Замкнутость КС-языков: есть для объединения и звезды, нет для пересечения и дополнения. Граница перед контекстно-зависимыми языками.

7. 7 Машина Тьюринга и вычислимость

   1. Машина Тьюринга: определение

      Определение машины Тьюринга: бесконечная лента, головка чтения-записи, функция переходов, принятие и остановка. Конфигурации и язык машины.

   2. Тезис Чёрча-Тьюринга

      Тезис Чёрча-Тьюринга: что значит «вычислимо». Эквивалентность моделей вычисления, почему тезис не теорема, а гипотеза о природе алгоритма.

   3. Разрешимость и проблема остановки

      Проблема остановки неразрешима: доказательство диагональным аргументом. Разрешимые и распознаваемые языки, что значит «алгоритма не существует».

   4. Сводимость задач

      Сводимость одной задачи к другой: как доказать неразрешимость через редукцию от проблемы остановки. Идея «если бы B решалась, решалась бы и A».

8. 8 Сложность и применения теории

   1. Классы P и NP

      Классы сложности P и NP: задачи, решаемые за полиномиальное время, и задачи с проверяемым за полином сертификатом. Примеры и интуиция.

   2. NP-полнота и проблема P=NP

      NP-полные задачи как самые трудные в NP, теорема Кука-Левина, проблема P=NP на миллион долларов и связь с олимпиадным программированием.

   3. Применения: лексеры и парсеры

      Где работает теория автоматов: лексический анализ конечными автоматами, синтаксический разбор КС-грамматиками, архитектура компилятора и regex-движки.

   4. Карта пройденного пути

      Итоговая карта курса теории вычислений: от алфавитов и автоматов через иерархию Хомского к вычислимости и сложности, единая картина и связи.