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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

Pushdown automation.png

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

(2) \Sigma — конечный входной алфавит;

(3) \Gamma — конечный алфавит магазинных символов;

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

(5) q_0\in Qначальное состояние управляющего устройства;


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


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

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

(1) q — текущее состояние управляющего устройства;

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

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

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

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

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

Языком, определяемым (или допускаемым) автоматом P (обозначается L(P)), называют множество цепочек, допускаемых автоматом P.

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

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

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


Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
  • Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.