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

Магазинный автомат — это конечный автомат, которому выдали стек. Ровно этой добавки хватает, чтобы распознавать контекстно-свободные языки.

Магазинный автомат (pushdown automaton, PDA) — конечный автомат, дополненный неограниченным стеком; на каждом шаге он читает символ входа, смотрит вершину стека и может класть/снимать символы стека.

Зачем стек

Конечный автомат провалился на aⁿbⁿ и скобках, потому что не мог «считать». Стек решает проблему: на каждой a кладём метку на стек, на каждой b — снимаем. Если в конце стек пуст, значит a и b было поровну. Стек — неограниченная память, но с дисциплиной LIFO (последним вошёл — первым вышел), что идеально подходит вложенности. Теорема: класс языков, распознаваемых магазинными автоматами, совпадает с классом КС-языков. PDA — машинный аналог КС-грамматики, как конечный автомат — аналог регулярки.

Как устроен переход

Переход PDA учитывает тройку: текущее состояние, входной символ (или ε) и символ на вершине стека. Результат — новое состояние и что сделать со стеком (снять вершину, заменить, добавить). PDA по определению недетерминирован, и это важно: недетерминированные PDA строго мощнее детерминированных (DPDA распознают меньший класс — на нём строят однозначные парсеры).

PDA для a^n b^n (n ≥ 1), стек с маркером дна Z:

фаза a:  (q0, a, Z) → (q0, AZ)    положить A
         (q0, a, A) → (q0, AA)    ещё A
фаза b:  (q0, b, A) → (q1, ε)     снять A (первая b)
         (q1, b, A) → (q1, ε)     снимать A
конец:   (q1, ε, Z) → (qf, Z)     стек пуст (только Z) ⇒ принять

идея: каждая a кладёт A, каждая b снимает A. Сошлось ⇒ принято.

Симуляция PDA на Python

Реализуем детерминированный PDA для aⁿbⁿ со стеком-списком. Кладём метку на a, снимаем на b, в конце проверяем пустоту.

def pda_anbn(word):
    stack = []
    phase = "a"          # сначала ждём a, потом b
    for ch in word:
        if ch == "a":
            if phase != "a":
                return False     # a после b — нельзя
            stack.append("A")    # push
        elif ch == "b":
            phase = "b"
            if not stack:
                return False     # b без парной a
            stack.pop()          # pop
        else:
            return False
    return len(stack) == 0 and phase == "b" or word == ""

for w in ["ab", "aabb", "aaabbb", "aab", "abb", "ba", "aabbb"]:
    print(f"{w:>7} -> {'принято' if pda_anbn(w) else 'отвергнуто'}")

Вывод:

     ab -> принято
   aabb -> принято
 aaabbb -> принято
    aab -> отвергнуто
    abb -> отвергнуто
     ba -> отвергнуто
  aabbb -> отвергнуто

«aab» отвергнуто (a больше, чем b — стек не пуст), «abb» отвергнуто (b больше — стек опустел рано). Стек сделал то, что конечному автомату не под силу: сосчитал и сравнил.

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

Почему один стек, а не два? PDA с двумя стеками эквивалентен машине Тьюринга — он мощнее и распознаёт уже не КС-языки, а всё вычислимое (два стека имитируют ленту). Один стек — золотая середина: достаточно для вложенности (скобки, выражения, разметка), но не для «тройного» подсчёта aⁿbⁿcⁿ (это уже не КС). Практические парсеры — это, по сути, детерминированные PDA: LR-парсер держит стек состояний и символов и принимает решения «push/pop/reduce», что прямо соответствует переходам PDA.

Частые ошибки

Забыть проверить пустоту стека в конце. Принятие требует не только дочитать вход, но и согласованного состояния стека (часто — его опустошения).

Считать DPDA и NPDA одинаковыми. Недетерминированный PDA мощнее: например, язык палиндромов {ww^R} распознаётся только NPDA (нужно «угадать» середину).

Думать, что стек даёт всё. Один стек = КС-языки, не больше. aⁿbⁿcⁿ стеку не по зубам — нужна лента (Тьюринг).

Итог

Магазинный автомат — конечный автомат + неограниченный стек (LIFO); переход учитывает вход и вершину стека.
Класс языков PDA в точности совпадает с КС-языками; PDA — машинный аналог КС-грамматики.
Недетерминированные PDA мощнее детерминированных (палиндромы — только NPDA).
Один стек = КС; два стека уже эквивалентны машине Тьюринга.