Определение. МАГАЗИННЫМ АВТОМАТОМ называется формальная система состоящая из 5 (6) объектов , где
— конечный алфавит входных знаков;
— конечное множество состояний магазинного автомата, где — заключительное состояние, — начальное состояние, если не оговорено особо;
— стековый алфавит.
— магазинное отображение множества декартового произведения множеств состояний магазинного автомата, стекового алфавита и входного алфавита в множество декартового произведения множеств состояний магазинного автомата, стекового алфавита [и выходного алфавита.
— есть множество команд следующего вида
, где — строка в стековом алфавите .
, где — начальная конфигурация магазинного автомата.
— выходной алфавит магазинного автомата.

Не трудно нарисовать внешний вид (структуру) магазинного автомата.
Магазинный автомат состоит из:
1. Устройства управления, реализующего систему команд и имеющего состояние .
2. Входной очереди .
3. Стека .
4. Выходной очереди .
Тогда структура магазинного автомата будут выглядеть следующим образом

Где из входной очереди в устройство управления могут поступать по одному знаки, то есть обозревается только конец очереди. В выходную очередь может записываться только один знак. Стек обозревается на глубину одного знака, но запись может производиться на произвольной глубине стека.
Дисциплина доступа к очереди FIFO, к стеку LIFO.

Определение. КОНФИГУРАЦИЕЙ МАГАЗИННОГО АВТОМАТА называется выражение , где
— состояние устройства управления,
— состояние стека.

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

e-ПЕРЕМЕЩЕНИЕ МАГАЗИННОГО АВТОМАТА

е-перемещение магазинного автомата существует четырех видов:
1 рода . Осуществляется командами вида .Не извлекается знак в 1 такт работы магазинного автомата.
2 рода. Осуществляется командами вида . Извлекается знак из входной очереди, но не извлекается знак из стека.
3 рода. Осуществляется командами вида . Состояние стека не изменяется, то есть извлеченный знак из стека тут же заносится обратно в стек.
4 рода. Осуществляется командами вида . В стек заносится строка

Определение. МНОЖЕСТВО ПРИНИМАЕМЫХ МАГАЗИННЫМ АВТОМАТОМ СТРОК — есть такое множество строк в алфавите , при подаче которых на вход магазинного автомата, магазинный автомат перейдет из начальной конфигурации в заключительную, года состояние устройства управления .

В этом случае строка называется СТРОКОЙ, ПРИНИМАЕМОЙ (РАСПОЗНАННОЙ) МАГАЗИННЫМ АВТОМАТОМ.

Магазинный автомат распознает (принимает) язык если принимает все его строки и не принимает (не распознает) строки не принадлежащие языку .

Пример. Рассмотрим магазинный автомат, распознающий строки, одинаково читаемые как слева на право, так и справа налево.

— входной алфавит,
— множество состояний,
— алфавит стека, где * — ограничитель стека,
система команд
— начальная конфигурация (* — есть аксиома языка ).

Рассмотрим строку . Подадим ее на вход магазинного автомата , тогда результат обработки этой строки представим в виде таблицы.

Таким образом видно , что данный автомат принял заданную строку.
Очевидно, что рассмотренный автомат принимает все “зеркальные строки” и является недетерминированным так как не является функцией и переход из состояния в состояние должен произойти на середине строки.
Очевидно, что какой — нибудь из автоматов, полученный в результате размножения при альтернативном выборе команд остановится, если строка “ зеркальна ” и ни один из автоматов не остановится в противном случае.