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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 5 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Автомат с магазинной памятью''' ([[Pushdown automation]]) --- тип [[Распознаватель|распознавателей]], определяющий класс
'''Автомат с магазинной памятью''' ([[Pushdown automation]]) тип [[Распознаватель|распознавателей]], определяющий класс
[[Контекстно-свободный язык|контекстно-свободных языков]].
[[Контекстно-свободный язык|контекстно-свободных языков]].


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


(1) <math>Q</math> --- конечное множество символов ''состояний'',
[[Файл:Pushdown automation.png|300px|right]]
 
(1) <math>Q</math> конечное множество символов ''состояний'',
представляющих возможные состояния управляющего устройства;
представляющих возможные состояния управляющего устройства;


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


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


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


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




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




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


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


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


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


(3) <math>\alpha</math> --- содержимое магазина; самый левый символ
(3) <math>\alpha</math> содержимое магазина; самый левый символ
цепочки считается верхним символом магазина; если <math>\alpha
цепочки считается верхним символом магазина; если <math>\alpha
=e</math>, то магазин считается пустым.
=e</math>, то магазин считается пустым.
Строка 41: Строка 43:
конфигурация вида <math>(q_0,\omega, Z_0)</math>, где
конфигурация вида <math>(q_0,\omega, Z_0)</math>, где
<math>\omega\in\Sigma^*</math>. ''Заключительная'' его конфигурация
<math>\omega\in\Sigma^*</math>. ''Заключительная'' его конфигурация
--- это конфигурация вида <math>(q,e,e)</math>, где <math>q\in F</math>.
это конфигурация вида <math>(q,e,e)</math>, где <math>q\in F</math>.


''Такт'' работы МП-автомата <math>P</math> представляется в виде
''Такт'' работы МП-автомата <math>P</math> представляется в виде
Строка 54: Строка 56:
<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: Строка 70:
верхний элемент магазина.
верхний элемент магазина.


Такт работы некоторого [[МП-автомат|МП-автомата]] <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>, говорит о том, что
МП-автомат <math>P</math>, находясь в состоянии <math>q</math> и имея <math>a</math> в
МП-автомат <math>P</math>, находясь в состоянии <math>q</math> и имея <math>a</math> в
качестве текущего входного символа, расположенного под
качестве текущего входного символа, расположенного под
входной головкой (т.е. обозревая <math>a</math>), а <math>Z</math> --- в качестве
входной головкой (т.е. обозревая <math>a</math>), а <math>Z</math> в качестве
верхнего символа магазина, может перейти в новое состояние
верхнего символа магазина, может перейти в новое состояние
<math>q'</math>, сдвинуть входную головку на одну ячейку вправо и
<math>q'</math>, сдвинуть входную головку на одну ячейку вправо и
Строка 90: Строка 92:
==Литература==
==Литература==


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




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

Текущая версия от 12:56, 17 ноября 2010

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

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

Pushdown automation.png

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