В отличие от обычных конечных автоматов, автомат с магазинной памятью является набором[1]
где
K — конечное множество состояний автомата,
— единственно допустимое начальное состояние автомата,
— множество конечных состояний, причём допустимо F=Ø и F=K,
Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом,
S — алфавит памяти (магазина),
— нулевой символ памяти.
Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением . То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует , в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с в левой части.
Класс языков, распознаваемых автоматами с магазинной памятью, совпадает с классом контекстно-свободных языков.
В чистом виде автоматы с магазинной памятью используются крайне редко. Обычно эта модель используется для наглядного представления отличия обычных конечных автоматов от синтаксических грамматик. Реализация автоматов с магазинной памятью отличается от конечных автоматов тем, что текущее состояние автомата сильно зависит от любого предыдущего.
Пример с использованием автомата с магазинной памятью
Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1.
Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 743 с. — ISBN 5-7038-2886-4.