Аноним

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

Материал из 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>-такте
Анонимный участник