EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#магазинный автомат#стек#формальные языки#контекстно-свободная грамматика#теория автоматов
Магазинный автомат: стек, переходы и примеры

Магазинный автомат - это модель вычисления, которая читает входную строку и помимо конечного управления использует стек, или магазин. Стек помогает помнить незавершённые вложенные конструкции: открыли скобку - положили метку, встретили закрывающую - сняли. Поэтому автомат способен проверять вложенность произвольной глубины, которой обычному конечному автомату в общем случае не запомнить. В интерактивной модели можно выбрать число пар скобок и проследить, как меняется высота стека после каждого символа.

Зачем автомату магазин

Представим строку из скобок. Для проверки недостаточно посчитать общее число открывающих и закрывающих: в строке )( их поровну, но первая же закрывающая скобка не имеет пары. Нужно помнить, сколько открытых скобок ещё ждут закрытия, и проверять порядок при чтении слева направо. Для нескольких видов скобок понадобится помнить и их тип: закрывающая должна соответствовать последней открытой.

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

При чтении строки ((())) стек растёт до трёх символов и затем пустеет; после последнего шага ролик показывает обратный просмотр трассы.

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

Из чего состоит модель

В распространённой записи магазинный автомат задают семёркой M=(Q,Σ,Γ,δ,q0,Z0,F)M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F). Здесь QQ - конечное множество состояний, Σ\Sigma - входной алфавит, Γ\Gamma - алфавит стека, q0q_0 - начальное состояние, Z0Z_0 - начальный символ стека, а FF - множество принимающих состояний. Функция переходов δ\delta описывает допустимые шаги.

Есть и другие соглашения: например, в учебной модели стек изначально пуст, а знак дна не изображают. Важно не смешивать обозначения внутри одного решения. Ниже Z0Z_0 служит неснимаемой меткой дна; говоря «пустой рабочий стек», мы имеем в виду, что над ней ничего нет.

Конфигурация фиксирует три вещи: текущее состояние, непрочитанный суффикс входа и содержимое стека. Состояние само по себе не определяет дальнейшую работу: при одной и той же входной букве возможный шаг зависит и от вершины. В отличие от моделей с фиксированным конечным числом состояний, стек может расти с длиной входа. Для сравнения ролей состояния и выхода см. автоматы Мура и Мили.

Как читать переход

Пусть вершина стека записана слева. Обозначение

δ(q,a,X)∋(p,YX)\delta(q, a, X)\ni(p, YX)

означает: в состоянии qq прочитать символ aa, снять с вершины XX, затем заменить его строкой YXYX и перейти в pp. Теперь сверху лежит YY, под ним - прежний XX. Переход может и просто снять XX: тогда вместо YXYX записывают ε\varepsilon, пустую строку. Какой конец записи является вершиной, автор задачи должен оговорить: в разных учебниках порядок отличается.

Входной аргумент ε\varepsilon означает шаг без чтения очередного символа. Он полезен, например, для перехода в принимающее состояние после проверки метки дна. Но ε\varepsilon не является обычным символом входного алфавита. В недетерминированной модели для одной ситуации может быть несколько допустимых переходов; вход принимается, если хотя бы одна полная ветвь вычисления принимает его. Если шага нет, соответствующая ветвь останавливается.

Пример: правильные скобочные последовательности

Рассмотрим алфавит Σ={(,)}\Sigma=\{(,)\} и одну метку XX в рабочей части стека. Алгоритм начинается с Z0Z_0. На каждой открывающей скобке он кладёт XX поверх текущей вершины; на закрывающей снимает один XX. Если встретилась закрывающая скобка, а сверху только Z0Z_0, допустимого перехода нет и строка отвергается.

Для входа ((())) достаточно посчитать рабочие метки после каждого шага:

ПрочитаноНачало((((((((()((())((()))
Меток XX0123210
Высота стека для строки из трёх открывающих и трёх закрывающих скобок: максимум три и возврат к нулю
Высота стека для строки из трёх открывающих и трёх закрывающих скобок: максимум три и возврат к нулю

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

Для круглых и квадратных скобок нужны разные метки. Например, после ([ наверху будет метка квадратной скобки: символ ) не вправе снять её. Стек хранит порядок незакрытых конструкций, а не только их количество. Модель с ползунками выше специально ограничена последовательностями вида (n)n\texttt{(}^{n}\texttt{)}^{n}: она показывает один маршрут, а не проверяет все возможные входы.

Пример языка aⁿbⁿ

Другой классический язык - L={anbn∣n≥0}L=\{a^n b^n\mid n\ge 0\}. Сначала идут только буквы aa, затем столько же букв bb; пустая строка входит в язык. Автомат кладёт по метке за каждую aa, а после первой bb переходит в фазу снятия: каждая bb удаляет одну метку. Возвращаться к чтению aa уже нельзя.

Так aaabbb принимается: три метки добавлены и три сняты. Строка aab оставляет метку, abb пытается снять лишнюю, а abab нарушает порядок фаз. Конечный автомат не может распознать весь этот язык: при неограниченном nn ему понадобилось бы различать сколько угодно количеств уже прочитанных aa. Стек предоставляет такую память в виде числа меток.

Это не означает, что любой счёт автоматически требует стека. Например, чётность числа символов хранится в двух состояниях. Об устройстве и границах конечных распознавателей в терминах регулярных языков рассказывает теорема Клини.

Когда строка считается принятой

Есть два стандартных способа задать принятие. При принятии по конечному состоянию должна существовать вычислительная ветвь, которая прочитала весь вход и закончила в состоянии из FF; остаток стека при этом сам по себе не запрещён. При принятии по пустому стеку весь вход также должен быть прочитан, а стек - опустошён; конечное состояние в этом определении не играет роли.

Метка дна помогает обнаружить конец рабочей памяти. Чтобы в примере со скобками принять по конечному состоянию, автомат после чтения всего входа может перейти в принимающее состояние, когда сверху Z0Z_0. Для буквального принятия по пустому стеку он должен также снять саму метку дна. Одно лишь наличие Z0Z_0 на вершине означает пустой рабочий стек, но не буквально пустой стек.

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

Связь с грамматиками и пределы

Недетерминированные магазинные автоматы распознают в точности контекстно-свободные языки - те, которые задаются контекстно-свободными грамматиками. Например, правила S→(S)S∣εS\to (S)S\mid\varepsilon порождают правильные скобочные последовательности. Грамматика описывает, как строить строки, а автомат - как распознавать их, пользуясь стеком. Связь и оба способа принятия изложены в лекции Колумбийского университета.

Детерминированный магазинный автомат ограничен сильнее недетерминированного: не каждый контекстно-свободный язык распознаётся детерминированной версией. Один стек также не даёт произвольного доступа к сохранённым данным. Например, язык {anbncn∣n≥0}\{a^n b^n c^n\mid n\ge0\} не является контекстно-свободным и не распознаётся обычным одностековым магазинным автоматом. Реализация реального стека на массиве добавляет практические детали памяти; их разбирает статья о стеке на списке.

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

  • Проверять только итоговую высоту. Если закрывающая скобка появилась при пустом рабочем стеке, строка уже неверна, даже когда итоговые количества равны.
  • Забывать о полном чтении входа. Пустой стек или принимающее состояние посреди строки ещё не гарантируют принятие всей строки.
  • Путать метку дна с пустотой. Стек с одним Z0Z_0 не пуст буквально, хотя рабочая часть пуста.
  • Считать одну неудачную ветвь общим отказом. В недетерминированной модели достаточно одной принимающей ветви.
  • Игнорировать порядок в записи стека. Вершина слева или справа меняет смысл замены; соглашение надо указать заранее.

FAQ

Магазинный автомат - это конечный автомат со стеком?

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

Может ли он проверять вложенные скобки?

Да. Открывающие скобки оставляют в стеке метки, а закрывающие снимают соответствующие верхние метки. В конце входа незакрытых скобок остаться не должно.

Обязательно ли автомат детерминирован?

Нет. В общем определении допускается несколько переходов из одной конфигурации. Детерминированный вариант ограничивает выбор и распознаёт только часть контекстно-свободных языков.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Иерархия Хомского: типы грамматик и автоматы

Иерархия Хомского: типы грамматик и автоматы

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

8 ноября 20269 минут
Контекстно-свободная грамматика: правила и примеры

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

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

8 ноября 20269 минут
Обратная польская запись: как вычислять со стеком

Обратная польская запись: как вычислять со стеком

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

8 ноября 20268 минут
Регулярная грамматика: правила, примеры и автомат

Регулярная грамматика: правила, примеры и автомат

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

8 ноября 20269 минут
Автоматы Мура и Мили: отличия, формулы и примеры

Автоматы Мура и Мили: отличия, формулы и примеры

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

11 июня 20268 минут
Стек и очередь: чем LIFO отличается от FIFO

Стек и очередь: чем LIFO отличается от FIFO

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

24 сентября 20269 минут