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

Соберём весь курс в одну картину: как связаны автоматы, грамматики, вычислимость и сложность — и зачем эта связь нужна.

Главная идея курса: мощность памяти определяет класс распознаваемых языков, а пределы памяти превращаются в пределы вычислимости.

Единая лестница

Мы прошли от простейшей машины к пределу алгоритмического. На каждой ступени росла память, и вместе с ней — класс языков. Вот вся карта на одной диаграмме:

память            машина              язык (Хомский)       пример
─────────────────────────────────────────────────────────────────────
нет               конечный автомат    регулярные (тип 3)   a*b*, чётность
стек (LIFO)       магазинный автомат  КС (тип 2)           a^n b^n, скобки
лента (огранич.)  ЛО-автомат          контекстно-зав.(1)   a^n b^n c^n
лента (∞)         машина Тьюринга     рекурс.-перечисл.(0) всё вычислимое
─────────────────────────────────────────────────────────────────────
за пределами:  проблема остановки — неразрешима ВООБЩЕ

Регулярные = конечные автоматы = регулярки (теорема Клини). КС = магазинные автоматы = BNF-грамматики. Машина Тьюринга = предел вычислимого (тезис Чёрча-Тьюринга). Каждое равенство — отдельная глава курса.

Три великих «нельзя»

Курс — это во многом коллекция доказательств невозможного. Сведём их вместе:

Что нельзя	Инструмент доказательства
aⁿbⁿ регуляркой	лемма о накачке для регулярных
aⁿbⁿcⁿ КС-грамматикой	лемма о накачке для КС
решить проблему остановки	диагональный аргумент
(вероятно) решить SAT за полином	NP-полнота (открыто, P=?NP)

Три первых — доказанные невозможности, четвёртая — величайшая открытая гипотеза. Все они говорят об одном: у вычислений есть жёсткие границы, и их можно математически очертить.

Проверь себя: классификатор языков

Соберём знания в маленький «классификатор»: по описанию языка определим его место в иерархии. Это финальная проверка интуиции курса.

languages = [
    ("a*b*",            "регулярный",        "конечный автомат"),
    ("a^n b^n",         "КС (не регулярный)", "магазинный автомат"),
    ("сбаланс. скобки", "КС (не регулярный)", "магазинный автомат"),
    ("a^n b^n c^n",     "контекстно-завис.",  "ЛО-автомат"),
    ("проблема остановки", "неразрешимый",   "никакая (нет алгоритма)"),
]
print(f"{'язык':<20}{'класс':<22}{'машина'}")
print("-" * 70)
for name, cls, machine in languages:
    print(f"{name:<20}{cls:<22}{machine}")

Вывод:

язык                класс                 машина
----------------------------------------------------------------------
a*b*                регулярный            конечный автомат
a^n b^n             КС (не регулярный)    магазинный автомат
сбаланс. скобки     КС (не регулярный)    магазинный автомат
a^n b^n c^n         контекстно-завис.     ЛО-автомат
проблема остановки  неразрешимый          никакая (нет алгоритма)

Если вы можете быстро отнести язык к нужной строке и назвать инструмент доказательства его границ — курс достиг цели.

Как работает под капотом

Почему эта теория не устарела за 90 лет? Потому что она про математические пределы, а не про технологии. Закон Мура ускоряет железо, но не делает неразрешимое разрешимым и не превращает экспоненту в полином. Каждый новый язык программирования Тьюринг-полон — значит, наследует ровно те же границы. Поэтому компиляторы по-прежнему строят на конечных автоматах и КС-грамматиках, криптография по-прежнему опирается на предполагаемую трудность NP-задач, а верификация — на замкнутость регулярных языков. Теория — это карта, по которой инженеры выбирают: какой инструмент достаточен, а какая задача в принципе за пределами достижимого.

Частые ошибки (итоговые)

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

Считать включения нестрогими. Регулярные ⊊ КС ⊊ контекстно-зависимые ⊊ рекурсивно-перечислимые — все включения строгие, что доказано леммами о накачке.

Думать, что «мощнее модель — всегда лучше». На практике берут минимально достаточную модель: лексеру хватит конечного автомата, и это эффективнее, чем тащить парсер.

Итог

Память определяет класс языка: нет памяти → регулярные, стек → КС, лента → вычислимое; за пределами — неразрешимое.
Ключевые равенства: регулярки = автоматы (Клини), КС = магазинные = BNF, машина Тьюринга = предел вычислимого (Чёрч-Тьюринг).
Три доказанных «нельзя» (накачка ×2, диагональ) и одна открытая гипотеза (P=?NP) очерчивают границы вычислений.
Теория про математические пределы — она не устаревает и определяет архитектуру компиляторов, regex, криптографии и верификации.