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

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

Автомат с магазинной памятью (сокращенно МП-автомат) --- это семерка [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].

Языком, определяемым (или допускаемым) {\it автоматом} [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], то верхний символ удаляется из магазина и, тем самым, магазинный список {\it сокращается}.

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

{[Ахо-Ульман], [Касьянов/95], [Касьянов-Поттосин]}