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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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> --- отображение множества <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>, то магазин считается пустым.
Строка 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>(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>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>.


Строка 70: Строка 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>, сдвинуть входную головку на одну ячейку вправо и
Строка 92: Строка 92:
==Литература==
==Литература==


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




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

Навигация