4194
правки
Автомат с магазинной памятью: различия между версиями
Перейти к навигации
Перейти к поиску
Автомат с магазинной памятью (посмотреть исходный код)
Версия от 12:56, 17 ноября 2010
, 17 ноября 2010нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>, где | ||
[[Файл:Pushdown automation.png|300px|right]] | [[Файл:Pushdown automation.png|300px|right]] | ||
(1) <math>Q</math> | (1) <math>Q</math> — конечное множество символов ''состояний'', | ||
представляющих возможные состояния управляющего устройства; | представляющих возможные состояния управляющего устройства; | ||
(2) <math>\Sigma</math> | (2) <math>\Sigma</math> — конечный ''входной'' алфавит; | ||
(3) <math>\Gamma</math> | (3) <math>\Gamma</math> — конечный алфавит ''магазинных'' символов; | ||
(4) <math>\delta</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>, то магазин считается пустым. | ||
| Строка 43: | Строка 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>P</math> представляется в виде | ''Такт'' работы МП-автомата <math>P</math> представляется в виде | ||
| Строка 56: | Строка 56: | ||
<math>\vdash_P</math>. | <math>\vdash_P</math>. | ||
Цепочка <math>\omega</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>. | ||
| Строка 70: | Строка 70: | ||
верхний элемент магазина. | верхний элемент магазина. | ||
Такт работы некоторого | Такт работы некоторого МП-автомата <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>, сдвинуть входную головку на одну ячейку вправо и | ||
| Строка 92: | Строка 92: | ||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. | * Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | ||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. | * Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | ||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. | * Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | ||
[[Категория:Теория автоматов]] | [[Категория:Теория автоматов]] | ||