Автомат с магазинной памятью: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 2: Строка 2:
[[Контекстно-свободный язык|контекстно-свободных языков]].
[[Контекстно-свободный язык|контекстно-свободных языков]].


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


Строка 54: Строка 54:
<math>\vdash_P</math>.
<math>\vdash_P</math>.


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


Строка 68: Строка 68:
верхний элемент магазина.
верхний элемент магазина.


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


Такт, в котором <math>a=e</math>, называют ''е-тактом''. В <math>e</math>-такте
Такт, в котором <math>a=e</math>, называют ''е-тактом''. В <math>e</math>-такте

Версия от 21:01, 16 апреля 2009

Автомат с магазинной памятью (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].

Языком, определяемым (или допускаемым) автоматом [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]-такт может происходить и тогда, когда вся входная цепочка прочитана.


Литература

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