Магазинный автомат: стек, переходы и примеры

Магазинный автомат - это модель вычисления, которая читает входную строку и помимо конечного управления использует стек, или магазин. Стек помогает помнить незавершённые вложенные конструкции: открыли скобку - положили метку, встретили закрывающую - сняли. Поэтому автомат способен проверять вложенность произвольной глубины, которой обычному конечному автомату в общем случае не запомнить. В интерактивной модели можно выбрать число пар скобок и проследить, как меняется высота стека после каждого символа.
Зачем автомату магазин
Представим строку из скобок. Для проверки недостаточно посчитать общее число открывающих и закрывающих: в строке )( их поровну, но первая же закрывающая скобка не имеет пары. Нужно помнить, сколько открытых скобок ещё ждут закрытия, и проверять порядок при чтении слева направо. Для нескольких видов скобок понадобится помнить и их тип: закрывающая должна соответствовать последней открытой.
Магазинный автомат решает эту задачу с помощью стека. К его вершине можно обратиться на каждом шаге: положить символ, снять его или заменить другим набором символов. Доступ к произвольному элементу в глубине не предусмотрен. Это правило «последним пришёл - первым ушёл» подробно разобрано в статье про стек и очередь.
На видео золотым отмечены текущая позиция входа и верхний элемент стека. Возврат от конца к началу нужен для повторного просмотра: это не обратные переходы распознавателя. Сам автомат читает вход только слева направо. Начальная конфигурация содержит непрочитанный вход и пустой рабочий стек, а последняя - прочитанный вход и пустой стек.
Из чего состоит модель
В распространённой записи магазинный автомат задают семёркой . Здесь - конечное множество состояний, - входной алфавит, - алфавит стека, - начальное состояние, - начальный символ стека, а - множество принимающих состояний. Функция переходов описывает допустимые шаги.
Есть и другие соглашения: например, в учебной модели стек изначально пуст, а знак дна не изображают. Важно не смешивать обозначения внутри одного решения. Ниже служит неснимаемой меткой дна; говоря «пустой рабочий стек», мы имеем в виду, что над ней ничего нет.
Конфигурация фиксирует три вещи: текущее состояние, непрочитанный суффикс входа и содержимое стека. Состояние само по себе не определяет дальнейшую работу: при одной и той же входной букве возможный шаг зависит и от вершины. В отличие от моделей с фиксированным конечным числом состояний, стек может расти с длиной входа. Для сравнения ролей состояния и выхода см. автоматы Мура и Мили.
Как читать переход
Пусть вершина стека записана слева. Обозначение
означает: в состоянии прочитать символ , снять с вершины , затем заменить его строкой и перейти в . Теперь сверху лежит , под ним - прежний . Переход может и просто снять : тогда вместо записывают , пустую строку. Какой конец записи является вершиной, автор задачи должен оговорить: в разных учебниках порядок отличается.
Входной аргумент означает шаг без чтения очередного символа. Он полезен, например, для перехода в принимающее состояние после проверки метки дна. Но не является обычным символом входного алфавита. В недетерминированной модели для одной ситуации может быть несколько допустимых переходов; вход принимается, если хотя бы одна полная ветвь вычисления принимает его. Если шага нет, соответствующая ветвь останавливается.
Пример: правильные скобочные последовательности
Рассмотрим алфавит и одну метку в рабочей части стека. Алгоритм начинается с . На каждой открывающей скобке он кладёт поверх текущей вершины; на закрывающей снимает один . Если встретилась закрывающая скобка, а сверху только , допустимого перехода нет и строка отвергается.
Для входа ((())) достаточно посчитать рабочие метки после каждого шага:
| Прочитано | Начало | ( | (( | ((( | ((() | ((()) | ((())) |
|---|---|---|---|---|---|---|---|
| Меток | 0 | 1 | 2 | 3 | 2 | 1 | 0 |

Максимальная высота рабочего стека равна трём: столько скобок одновременно осталось открытыми. После шестого символа вход исчерпан, а над нет меток, поэтому строка принимается. Пустая строка тоже правильная: ни одной незакрытой скобки нет. В отличие от этого, строка (() заканчивается с одной меткой, а строка )( застревает на первом символе. Равенство общего числа скобок здесь не спасает.
Для круглых и квадратных скобок нужны разные метки. Например, после ([ наверху будет метка квадратной скобки: символ ) не вправе снять её. Стек хранит порядок незакрытых конструкций, а не только их количество. Модель с ползунками выше специально ограничена последовательностями вида : она показывает один маршрут, а не проверяет все возможные входы.
Пример языка aⁿbⁿ
Другой классический язык - . Сначала идут только буквы , затем столько же букв ; пустая строка входит в язык. Автомат кладёт по метке за каждую , а после первой переходит в фазу снятия: каждая удаляет одну метку. Возвращаться к чтению уже нельзя.
Так aaabbb принимается: три метки добавлены и три сняты. Строка aab оставляет метку, abb пытается снять лишнюю, а abab нарушает порядок фаз. Конечный автомат не может распознать весь этот язык: при неограниченном ему понадобилось бы различать сколько угодно количеств уже прочитанных . Стек предоставляет такую память в виде числа меток.
Это не означает, что любой счёт автоматически требует стека. Например, чётность числа символов хранится в двух состояниях. Об устройстве и границах конечных распознавателей в терминах регулярных языков рассказывает теорема Клини.
Когда строка считается принятой
Есть два стандартных способа задать принятие. При принятии по конечному состоянию должна существовать вычислительная ветвь, которая прочитала весь вход и закончила в состоянии из ; остаток стека при этом сам по себе не запрещён. При принятии по пустому стеку весь вход также должен быть прочитан, а стек - опустошён; конечное состояние в этом определении не играет роли.
Метка дна помогает обнаружить конец рабочей памяти. Чтобы в примере со скобками принять по конечному состоянию, автомат после чтения всего входа может перейти в принимающее состояние, когда сверху . Для буквального принятия по пустому стеку он должен также снять саму метку дна. Одно лишь наличие на вершине означает пустой рабочий стек, но не буквально пустой стек.
Для недетерминированных магазинных автоматов эти способы эквивалентны по классу распознаваемых языков: автомат одного типа можно преобразовать в автомат другого. Это утверждение о возможности построить другую машину, а не о том, что два условия совпадают для одной и той же таблицы переходов.
Связь с грамматиками и пределы
Недетерминированные магазинные автоматы распознают в точности контекстно-свободные языки - те, которые задаются контекстно-свободными грамматиками. Например, правила порождают правильные скобочные последовательности. Грамматика описывает, как строить строки, а автомат - как распознавать их, пользуясь стеком. Связь и оба способа принятия изложены в лекции Колумбийского университета.
Детерминированный магазинный автомат ограничен сильнее недетерминированного: не каждый контекстно-свободный язык распознаётся детерминированной версией. Один стек также не даёт произвольного доступа к сохранённым данным. Например, язык не является контекстно-свободным и не распознаётся обычным одностековым магазинным автоматом. Реализация реального стека на массиве добавляет практические детали памяти; их разбирает статья о стеке на списке.
Частые ошибки
- Проверять только итоговую высоту. Если закрывающая скобка появилась при пустом рабочем стеке, строка уже неверна, даже когда итоговые количества равны.
- Забывать о полном чтении входа. Пустой стек или принимающее состояние посреди строки ещё не гарантируют принятие всей строки.
- Путать метку дна с пустотой. Стек с одним не пуст буквально, хотя рабочая часть пуста.
- Считать одну неудачную ветвь общим отказом. В недетерминированной модели достаточно одной принимающей ветви.
- Игнорировать порядок в записи стека. Вершина слева или справа меняет смысл замены; соглашение надо указать заранее.
FAQ
Магазинный автомат - это конечный автомат со стеком?
Да, как интуитивное описание: управление имеет конечное число состояний, а стек служит дополнительной неограниченной в теоретической модели памятью. Формальные варианты отличаются деталями переходов и принятия.
Может ли он проверять вложенные скобки?
Да. Открывающие скобки оставляют в стеке метки, а закрывающие снимают соответствующие верхние метки. В конце входа незакрытых скобок остаться не должно.
Обязательно ли автомат детерминирован?
Нет. В общем определении допускается несколько переходов из одной конфигурации. Детерминированный вариант ограничивает выбор и распознаёт только часть контекстно-свободных языков.
Коротко
Магазинный автомат сочетает конечное управление со стеком. Переход зависит от состояния, входа и вершины стека, поэтому модель удобна для вложенных конструкций. При разборе проверяют каждую конфигурацию, полное чтение входа и точно оговорённое условие принятия.
Читайте также

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

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

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

Регулярная грамматика: правила, примеры и автомат
Регулярная грамматика простыми словами: как устроены праволинейные правила, как вывести слово, построить конечный автомат и проверить границы модели на примерах.

Автоматы Мура и Мили: отличия, формулы и примеры
Автоматы Мура и Мили простыми словами: чем отличаются выходы, как строить граф и таблицу переходов, как преобразовать один тип в другой и почему выходные строки сдвинуты на такт.

Стек и очередь: чем LIFO отличается от FIFO
Стек и очередь рядом: дисциплины LIFO и FIFO и порядок выхода элементов, очередь на кольцевом буфере за O(1), дек, таблица сложности операций и примеры применения.