38
правок
Изменения
Нет описания правки
{{Определение
|definition =
Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как <b>детерминированный автомат с магазинной (стековой) памятью</b>, где <br>
* <tex>Q</tex>: конечное множество состояний.
* <tex>\Sigma</tex>: конечное множество входных символов.
* <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазин.
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где для кадой тройки <tex>(q,a,X)</tex> пара <tex>(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>: множество допускающих состояний.
}}
{{Определение|definition =Определим <b>детерминированный автомат с магазинной (стековой) памятью</b> как автомат с магазинной памятью, в котором <br>#<tex>\delta (q,a,X)</tex> имеет не более одного элемента для каждого <tex>q \in Q, a \in \Sigma</tex> или <tex>a=\epsilon, X \in \Gamma</tex>.#Если <tex>\delta (q,a,X)</tex> непусто для некоторого <tex>a \in \Sigma</tex>, то <tex>\delta (q,\epsilon,X)</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>.
