Автомат с магазинной памятью: различия между версиями
Перейти к навигации
Перейти к поиску
Автомат с магазинной памятью (посмотреть исходный код)
Версия от 14:01, 16 апреля 2009
, 16 апреля 2009нет описания правки
Нет описания правки |
|||
| Строка 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>, то верхний символ | ||
удаляется из магазина и, тем самым, магазинный список | удаляется из магазина и, тем самым, магазинный список ''сокращается''. | ||
сокращается | |||
Такт, в котором <math>a=e</math>, называют ''е-тактом''. В <math>e</math>-такте | Такт, в котором <math>a=e</math>, называют ''е-тактом''. В <math>e</math>-такте | ||