Детерминированные автоматы с магазинной памятью — различия между версиями
(Новая страница: «{{Определение |definition = Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как <b>детерминированный автомат…») |
|||
Строка 7: | Строка 7: | ||
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где | * <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где | ||
** <tex>q</tex>: текущее состояние из Q. | ** <tex>q</tex>: текущее состояние из Q. | ||
− | ** <tex>a</tex>: | + | ** <tex>a</tex>: входной символ. |
** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>. | ** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>. | ||
** <tex>p</tex>: новое состояние из Q. | ** <tex>p</tex>: новое состояние из Q. | ||
Строка 15: | Строка 15: | ||
* <tex>F</tex>: множество допускающих состояний. | * <tex>F</tex>: множество допускающих состояний. | ||
}} | }} | ||
+ | |||
+ | Будем обозначать переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_2,a_2,X_2)</tex> как <tex>(q_1,a_1,X_1)\vdash(q_2,a_2,X_2)</tex>. Переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_{p+1},a_{p+1},X_{p+1})</tex> через <tex>P</tex> промежуточных состояний обозначаем <tex>(q_1,a_1,X_1)\vdash^*_P(q_{p+1},a_{p+1},X_{p+1})</tex>. | ||
+ | |||
+ | ==Пример== | ||
+ | Автомат <tex>P=(\{q,p\},\{0,1\},\{Z_0,X\},\delta,q,Z_0,\{p\})</tex> с функией перехода <tex>\delta</tex>: | ||
+ | # <tex>\delta(q,0,Z_0)=(q,XZ_0)</tex> | ||
+ | # <tex>\delta(q,0,X)=(q,XX)</tex> | ||
+ | # <tex>\delta(q,1,X)=(q,X)</tex> | ||
+ | # <tex>\delta(q,0,Z_0)=(p,Z_0)</tex> | ||
+ | # <tex>\delta(p,0,Z_0)=(p,XZ_0)</tex> | ||
+ | # <tex>\delta(p,0,X)=(p,XX)</tex> | ||
+ | # <tex>\delta(p,1,X)=(p,X)</tex> | ||
+ | [[Файл:МП-автомат.png]] |
Версия 06:41, 15 января 2011
Определение: |
Определим
| как детерминированный автомат с магазинной (стековой) памятью, где
Будем обозначать переход автомата из состояния в состояние как . Переход автомата из состояния в состояние через промежуточных состояний обозначаем .
Пример
Автомат
с функией перехода :