Автомат с магазинной памятью

Автомат с магазинной памятью (Pushdown automaton) — тип абстрактной машины, определяющий класс контекстно-свободных языков.

Автомат с магазинной памятью (сокращенно МП-автомат ) — это семерка [math]\displaystyle{ P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) }[/math], где

(1) [math]\displaystyle{ Q }[/math] — конечное множество символов состояний, представляющих возможные состояния управляющего устройства;

(2) [math]\displaystyle{ \Sigma }[/math] — конечный входной алфавит;

(3) [math]\displaystyle{ \Gamma }[/math] — конечный алфавит магазинных символов;

(4) [math]\displaystyle{ \delta }[/math] — отображение множества [math]\displaystyle{ Q\times(\Sigma\cup\{ e\})\times\Gamma }[/math] в множество конечных подмножеств множества [math]\displaystyle{ Q\times \Gamma^* }[/math];

(5) [math]\displaystyle{ q_0\in Q }[/math] — начальное состояние управляющего устройства;

(6) [math]\displaystyle{ Z_0\in \Gamma }[/math] — символ, находящийся в магазине в начальный момент (начальный символ);

(7) [math]\displaystyle{ F\subseteq Q }[/math] — множество заключительных состояний.

Конфигурацией МП-автомата [math]\displaystyle{ P }[/math] называется тройка [math]\displaystyle{ (q,\omega,\alpha)\in Q\times\Sigma^*\times\Gamma^* }[/math], где

(1) [math]\displaystyle{ q }[/math] — текущее состояние управляющего устройства;

(2) [math]\displaystyle{ \omega }[/math] — неиспользованная часть входной цепочки; первый символ цепочки [math]\displaystyle{ \omega }[/math] находится под входной головкой; если [math]\displaystyle{ \omega =e }[/math], то считается, что вся входная лента прочитана;

(3) [math]\displaystyle{ \alpha }[/math] — содержимое магазина; самый левый символ цепочки считается верхним символом магазина; если [math]\displaystyle{ \alpha =e }[/math], то магазин считается пустым.

Начальной конфигурацией МП-автомата [math]\displaystyle{ P }[/math] называется конфигурация вида [math]\displaystyle{ (q_0,\omega, Z_0) }[/math], где [math]\displaystyle{ \omega\in\Sigma^* }[/math]. Заключительная его конфигурация — это конфигурация вида [math]\displaystyle{ (q,e,e) }[/math], где [math]\displaystyle{ q\in F }[/math].

Такт работы МП-автомата [math]\displaystyle{ P }[/math] представляется в виде бинарного отношения [math]\displaystyle{ \vdash_P }[/math], определенного на конфигурациях следующим образом: [math]\displaystyle{ (q, }[/math] [math]\displaystyle{ a\omega, }[/math] [math]\displaystyle{ Z\alpha)\vdash_P (p,\omega,\gamma\alpha) }[/math], если множество [math]\displaystyle{ \delta(q,a,Z) }[/math] содержит [math]\displaystyle{ (p, \gamma) }[/math], где [math]\displaystyle{ q,p\in Q, }[/math] [math]\displaystyle{ a\in\Sigma\cup\{ e\}, }[/math] [math]\displaystyle{ \omega\in\Sigma^*, }[/math] [math]\displaystyle{ Z\in\Gamma }[/math] и [math]\displaystyle{ \alpha,\gamma\in\Gamma^* }[/math]. Через [math]\displaystyle{ \vdash_P^* }[/math] и [math]\displaystyle{ \vdash_P^+ }[/math] обозначаются соответственно рефлексивное и транзитивное замыкание и транзитивное замыкание отношения [math]\displaystyle{ \vdash_P }[/math].

Цепочка [math]\displaystyle{ \omega }[/math] допускается МП-автоматом [math]\displaystyle{ P }[/math], если [math]\displaystyle{ (q_0,\omega,Z_0)\vdash_P^*(q,e,e) }[/math] для некоторого [math]\displaystyle{ q\in F }[/math].

Языком, определяемым (или допускаемым) автоматом [math]\displaystyle{ P }[/math] (обозначается [math]\displaystyle{ L(P) }[/math]), называют множество цепочек, допускаемых автоматом [math]\displaystyle{ P }[/math].

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

Такт работы некоторого МП-автомата [math]\displaystyle{ P }[/math], связанный с переходом от конфигурации [math]\displaystyle{ (q,a\omega,Za) }[/math] к конфигурации [math]\displaystyle{ (q',\omega,\gamma a) }[/math] при [math]\displaystyle{ a\neq e }[/math], говорит о том, что МП-автомат [math]\displaystyle{ P }[/math], находясь в состоянии [math]\displaystyle{ q }[/math] и имея [math]\displaystyle{ a }[/math] в качестве текущего входного символа, расположенного под входной головкой (т.е. обозревая [math]\displaystyle{ a }[/math]), а [math]\displaystyle{ Z }[/math] — в качестве верхнего символа магазина, может перейти в новое состояние [math]\displaystyle{ q' }[/math], сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой [math]\displaystyle{ \gamma }[/math] магазинных символов. Если [math]\displaystyle{ \gamma =e }[/math], то верхний символ удаляется из магазина и, тем самым, магазинный список сокращается.

Такт, в котором [math]\displaystyle{ a=e }[/math], называют е-тактом. В [math]\displaystyle{ e }[/math]-такте текущий входной символ не принимается во внимание и входная головка не сдвигается. Однако состояние управляющего устройства и содержимое памяти могут измениться. Заметим, что [math]\displaystyle{ e }[/math]-такт может происходить и тогда, когда вся входная цепочка прочитана.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
• Касьянов В.Н., Касьянова Е.В. Теория вычислений. — Новосибирск: НГУ, 2018.

• Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.