Просмотр кода страницы Автомат с магазинной памятью

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

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

[[Файл:Pushdown automation.png|300px|right]]

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

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

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

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

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


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


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

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

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

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

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

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

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

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

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

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

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

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


==Литература==

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


[[Категория:Теория автоматов]]