38
правок
Изменения
Нет описания правки
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где
** <tex>q</tex>: текущее состояние из Q.
** <tex>a</tex>: либо входной символ, либо пустая цепочка <tex>\epsilon</tex>.
** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>.
** <tex>p</tex>: новое состояние из Q.
* <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]]
