Магазинные автоматы, Мили и Мура
Play ITЗагрузка интерактивного демо…
Конечный автомат помнит только "где мы сейчас". Для вложенных конструкций — скобок, дерева вызовов, вложенных if — нужна память LIFO: последний открытый элемент закрывается первым. В теории это магазинный (стековый) автомат; в компиляторе — парсер со стеком нетерминалов.
Предшествующие темы: конечные автоматы, грамматики. Обзор: ТАФЯ.
Для читателя без математического фона
Магазинный автомат = конечный автомат + стек (LIFO: последним положили — первым сняли). Стек — та же идея, что при проверке скобок: открыли ( — положили на стек; закрыли ) — сняли и сверили пару.
| Задача | ДКА | МП-автомат |
|---|---|---|
| "строка из букв и цифр" | достаточно | достаточно |
"скобки () сбалансированы" | памяти не хватает | стек считает вложенность |
"выражение a + (b * c)" | — | парсер + грамматика |
Мили и Мура — про автоматы, которые что-то выдают на каждом шаге (сигнал, действие), а только "да/нет" в конце. Удобно для протоколов, UI state machines, прошивок.
Автоматы с магазинной памятью (МП-автомат, PDA)
МП-автомат — кортеж (в одной из распространённых форм):
M = (Q, Σ, Γ, δ, q₀, Z₀, F)
| Компонент | Смысл |
|---|---|
Q | состояния (как у ДКА) |
Σ | входной алфавит |
Γ | магазинный алфавит (символы стека) |
δ | переходы с операциями над стеком |
q₀ | начальное состояние |
Z₀ | дно стека (начальный символ) |
F | принимающие состояния |
На шаге автомат читает (или не читает) символ входа и заменяет вершину стека строкой символов из Γ.
Запись перехода (один из стандартов):
(q, a, X) ⊢ (q', γ) — в состоянии q, прочитав a (или ε), с вершиной стека X, перейти в q' и заменить X на строку γ (символы кладутся слева направо, верхний — первый символ γ).
Пример: при ( заменить Z₀ на ( Z₀ — маркер открытой скобки лежит над прежним дном.
Принятие по пустому стеку и по состоянию
- По финальному состоянию — как ДКА, плюс стек "не мешает".
- По пустому стеку — слово принято, если стек опустошён после обработки (удобно для "скобки сбалансированы").
Классы совпадают для недетерминированных МП-автоматов с обычными КС-языками.
Пример — сбалансированные скобки (), []
Идея переходов:
- Видим
(— кладём на стек маркер, переходим дальше. - Видим
)— если на вершине маркер(— снимаем, иначе отклонить. - В конце ввода — стек должен содержать только дно
Z₀.
Один тип скобок — можно свернуть к счётчику; два типа без стека (только конечные состояния) — не регулярный язык.
Пошагово — стек для (()())
| Символ | Действие | Стек (низ → верх) |
|---|---|---|
( | push | ( |
( | push | (, ( |
) | pop, совпало | ( |
( | push | (, ( |
) | pop, совпало | ( |
) | pop, совпало | пусто → принять |
Для (() после третьего символа стек (, вход кончился — отклонить.
Разбор — язык { aⁿbⁿ }
Идея МП-автомата:
- Читаем
a, кладём на стек символA(или считаем маркеры). - При первом
bпереходим в фазу "снимаем по одномуAна каждыйb". - Если
aпослеb, или стек не пуст при конце — отклонить. - Принять, если вход кончился и стек пуст (по дну
Z₀).
Это не регулярный язык — нужна неограниченная (в теории) глубина стека.
Детерминированный МП-автомат (ДМПА)
Не всякий КС-язык распознаётся детерминированным МП-автоматом. Языки, которые распознаются — LR(k), LL(k) — подкласс, на котором держится большинство компиляторов.
Следствие: "написать парсер вручную" часто = спроектировать детерминированный стековый автомат, а не общий недетерминированный PDA с угадыванием.
def parse_parens(s: str) -> bool:
"""МП-идея: стек открывающих скобок."""
stack: list[str] = []
pairs = {")": "(", "]": "[", "}": "{"}
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
Связь с КС-грамматиками
Теорема: язык контекстно-свободный (тип 2 по Хомскому) тогда и только тогда, когда распознаётся некоторым МП-автоматом.
| Направление | Смысл |
|---|---|
| Грамматика → PDA | недетерминированный автомат "угадывает" правило, кладёт нетерминалы на стек |
| PDA → грамматика | симулирует снятие/кладку стеком правилами A → … |
Парсеры LR/LL — детерминированные подклассы; не всякая КС-грамматика LR, но промышленные языки подгоняют под генераторы.
Понятие преобразователей
Преобразователь (трансдуктор) — автомат с выходом: на каждом переходе может печатать символы в выходную ленту (или в поток).
| Вид | Вход → выход |
|---|---|
| Регулярный трансдуктор | конечный автомат + выход на переходах — простые потоковые замены |
| Синтаксически ориентированный | дерево → код (обход AST после парсера) |
Компилятор: лексер (распознаватель) → парсер (распознаватель + структура) → генератор кода (преобразователь AST в инструкции). Трансдуктор в узком смысле — шаг "структура → другая структура".
Автоматы Мили и Мура
В конечном автомате часто говорят только "принять / не принять". В управлении и протоколах важно что выдать на каждом шаге. Два классических варианта:
Автомат Мили
Выход зависит от перехода (пара "из какого состояния → в какое" + входной символ).
λ : Q × Σ × Q → Γ_out (или на рёбрах графа подпись выхода)
Пример: по событию tick в состоянии Idle перейти в Work и выдать сигнал start_motor.
Автомат Мура
Выход зависит от состояния (в каждом состоянии свой выход, независимо от того, как в него вошли).
λ : Q → Γ_out
Пример: в состоянии Red светофор всегда "красный", пока не сменится состояние.
| Мили | Мура | |
|---|---|---|
| Выход на | переходе | состоянии |
| Число выходов при ` | Q | = n, |
| Преобразование | любой Мура → Мили (разбить состояние по выходам) | любой Мили → Мура (добавить промежуточные состояния) |
Равносильность: для конечных автоматов классы вычислимых реакций совпадают — любой автомат Мили можно переписать в эквивалентный Мура и наоборот (ценой роста числа состояний).
Преобразование Мили → Мура
Если на переходе (q, a, q') выход z, вводят промежуточное состояние q_* с выходом z в духе Мура: "вошли в переход — зафиксировали выход". Число состояний растёт, но для синтеза схем и верификации удобнее единый стиль.
Преобразование Мура → Мили
Каждое состояние q с выходом g(q) разбивают: переходы входят в q с меткой выхода на ребре "как при входе в q". Снова рост |Q|, зато события на рёбрах (удобно для логов "по какому событию сменили фазу").
Где встречается в IT
- Протоколы (TCP states, TLS handshake) — часто диаграммы Мили/Мура.
- UI state machines (XState, Redux reducers): состояние + действие на переходе — ближе к Мили.
- HDL / цифровая схема: выход регистра по текущему состоянию — Мура.
Не путать с законом Мура (транзисторы на чипе) — другая тема.
Эксперимент по распознаванию состояния
Задача: автомат в скрытом начальном состоянии q ∈ Q; вы подаёте входную последовательность и наблюдаете выходы (для Мили/Мура) или "принято/нет" (для распознавателя). Можно ли однозначно определить q?
| Ситуация | Результат |
|---|---|
| Состояния различаются ответами на одну и ту же входную цепочку | диагностическая последовательность существует |
| Состояния неразличимы | при минимизации ДКА сливаются в один класс |
В тестировании API — последовательность запросов как "вход", коды ответов как "выход" — поиск минимального сценария, отличающего "баг в auth" от "баг в cart".
Связь с конечными автоматами: минимальный ДКА уникален с точностью до переименования состояний.
Алгоритм минимизации (напоминание): строят таблицу различимости пар состояний; пары, не различаемые ни одной входной цепочкой, сливают. Для Мили/Мура добавляют сравнение выходных реакций — иначе два состояния с одинаковыми переходами, но разным "светофором", нельзя объединять.
Вложенные автоматы (иерархия в продукте)
Часто **стек машин:
- верхний уровень — сессия пользователя;
- внутри — подмашина оплаты;
- внутри — подмашина 3DS.
Это не один плоский КА: вложенность снова требует стека (или явного стека состояний в XState invoke). Теория оправдывает, почему "простая диаграмма из 5 кружков" ломается на реальных сценариях.
Сравнение уровней
| Модель | Память | Типичный пример |
|---|---|---|
| ДКА | ` | Q |
| МПА | ` | Q |
| МТ | лента | произвольная программа |
Практические выводы
- Парсер = МП-автомат + дерево; ошибка "ожидался
)" — стек показал несовпадение. - State machine в продукте без стека — обычно регулярный уровень; вложенные сценарии могут требовать явного стека (стек вызовов, вложенные машины).
- Выбор Мили vs Мура — вопрос удобства модели: действия на рёбрах (Мили) vs инварианты состояния (Мура).
Упражнение
- Проследите стек для входа
(()())по правилам скобок (вручную или черезparse_parensвыше). - Нарисуйте автомат Мура для светофора (Red / Yellow / Green) с таймерными переходами.
- В тестах API: придумайте короткую последовательность запросов, различающую "не авторизован" и "корзина пуста" (диагностика состояний).
Вопросы для самопроверки
- Чем стек МП-автомата отличается от "памяти" ДКА?
- Сформулируйте связь КС-грамматики и МП-автомата.
- Где выход в Мили, где в Муре?
- Почему любой автомат Мили можно преобразовать в автомат Мура?
- Что такое диагностическая последовательность для двух состояний?
Вернуться к обзору: Формальные языки и автоматы. Следующая тема блока: Теория информации.