Автоматы с магазинной памятью (PDA)

Каждый раз, когда IDE подчёркивает незакрытую скобку красным - под капотом работает автомат с магазинной памятью. Он «помнит» каждую открывающую скобку, вложенный if, каждый незакрытый тег. Конечный автомат на это не способен - ему не хватает памяти. PDA решает эту проблему одним элегантным дополнением: стеком.

• **Парсеры языков программирования** - GCC, Clang, V8 используют вариации PDA для разбора синтаксиса
• **Проверка скобок в IDE** - подсветка парных скобок, автозакрытие тегов в HTML
• **XML/JSON валидаторы** - проверка вложенности элементов - классическая задача для PDA
• **Стековые виртуальные машины** - JVM и Python VM основаны на стековой архитектуре, родственной PDA

Предварительные знания

• Context-Free Grammars (CFG)

PDA: автомат со стеком

**DFA не умеет считать.** Он может запомнить, что видел `a`, но не может запомнить, *сколько* `a` было. Поэтому DFA не справляется с {aⁿbⁿ} - нужно помнить количество, а конечная память закончится.

**Решение - добавить стек.** Pushdown Automaton (PDA) - это NFA с дополнительной структурой данных: стеком неограниченной глубины. Стек работает по принципу LIFO: последним вошёл - первым вышел.

Аналогия из жизни: **проверка скобок в коде**. Встретили `(` - кладём в стек. Встретили `)` - снимаем. Если в конце стек пуст - скобки сбалансированы.

**Ключевая идея:** стек даёт PDA возможность «запоминать» произвольное количество информации, но с ограничением - доступ только к верхнему элементу. Это строго мощнее конечного автомата, но слабее машины Тьюринга.

Формальное определение PDA

Формально, **PDA** - это семёрка **M = (Q, Σ, Γ, δ, q₀, Z₀, F)**:

Самое важное - **функция переходов δ**. На каждом шаге PDA смотрит на три вещи: текущее состояние, текущий входной символ (или ε), и верхний символ стека. На основе этого он выбирает: в какое состояние перейти и что положить в стек вместо снятого символа.

**Два режима принятия строки:** 1. **Accept by final state** - строка прочитана, автомат в состоянии из F 2. **Accept by empty stack** - строка прочитана, стек пуст Оба режима **эквивалентны по мощности** - можно преобразовать один в другой.

Построим PDA для {aⁿbⁿ | n ≥ 0} с принятием по пустому стеку:

Запись `a, X/γ` на стрелке PDA означает: «читаем a, снимаем X с вершины стека, кладём γ». Если γ = ε - просто снимаем (pop). Если γ = αX - кладём α поверх X (push α).

PDA в действии: три примера

Разберём три классических контекстно-свободных языка и PDA для каждого. Все три невозможно распознать конечным автоматом.

Пример 1: Палиндромы {wwᴿ | w ∈ {a,b}*}

Язык палиндромов чётной длины: `abba`, `aabbaa`, `baab`. Стратегия: push первую половину, pop вторую - если стек опустел, строка - палиндром.

Пример 2: Сбалансированные скобки

Пример 3: Python-симуляция PDA

Обратите внимание: PDA для палиндромов **недетерминированный** - он угадывает середину через ε-переход. Детерминированный PDA (DPDA) палиндромы чётной длины распознать НЕ может! Это важное отличие от DFA/NFA, где детерминизм не теряет мощности.

PDA и CFG: эквивалентность

Одна из красивейших теорем теории формальных языков: **PDA и CFG описывают в точности один и тот же класс языков** - контекстно-свободные языки. Каждую грамматику можно превратить в автомат и наоборот.

**Теорема эквивалентности:** Язык L является контекстно-свободным тогда и только тогда, когда существует PDA, распознающий L.

CFG → PDA: конструкция

Идея элегантна: PDA **моделирует leftmost derivation на стеке**. Нетерминал на вершине стека → заменяем по правилу. Терминал на вершине → сравниваем с входом.

DPDA vs NPDA: неожиданная асимметрия

Для конечных автоматов детерминизм не теряет мощности: DFA = NFA. Но для PDA ситуация **принципиально иная**!

**DPDA строго слабее NPDA!** Детерминированные КС-языки (DCFL) - собственное подмножество всех КС-языков. Однако для практических задач (парсинг языков программирования) DPDA обычно достаточно.

Ключевые идеи

• **PDA = NFA + стек** - бесконечный стек даёт возможность «считать» и проверять вложенность
• **PDA = (Q, Σ, Γ, δ, q₀, Z₀, F)** - семёрка с отдельным стековым алфавитом и начальным символом стека
• **Два режима принятия** - по конечному состоянию и по пустому стеку, эквивалентны по мощности
• **PDA ≡ CFG** - эквивалентны: любую грамматику можно превратить в PDA и наоборот
• **DPDA ⊊ NPDA** - в отличие от DFA/NFA, детерминированный PDA строго слабее недетерминированного

Связь с другими темами

PDA занимает центральное место в иерархии вычислительных моделей:

• Контекстно-свободные грамматики (CFG) — PDA и CFG эквивалентны - описывают один и тот же класс языков
• Алгоритм CYK — CYK - эффективный алгоритм проверки принадлежности строки КС-языку за O(n³)
• NFA и DFA — PDA расширяет NFA стеком; без стека PDA вырождается в NFA

Вопросы для размышления

• PDA имеет стек (LIFO), а что если дать автомату очередь (FIFO)? Оказывается, автомат с очередью эквивалентен машине Тьюринга! Почему очередь настолько мощнее стека?
• Языки программирования обычно являются DCFL (детерминированными КС-языками). Почему для компиляторов важна именно детерминированность?
• Если PDA и CFG эквивалентны, зачем нужны обе модели? В каких задачах удобнее грамматика, а в каких - автомат?

Связанные уроки

• fl-12-cfg — CFG и PDA эквивалентны - нужно понимать грамматику
• fl-14-cnf-gnf — CNF нужна для CYK, который заменяет PDA в парсинге
• fl-06-dfa — PDA = DFA + стек, нужно знать базовый автомат
• ds-03-stacks — Стек PDA - прямая реализация через data-structure стек
• comp-12-lr-parsing