editor
143
правки
Изменения
Нет описания правки
{{Определение
|definition =
<b> Автоматом Детерменированным автоматом с магазинной памятью </b> называется набор <tex> A = \langle\Sigma,Q,s\in Q, \Gamma, Z_0 \in \Gamma, T \subset Q, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow \cal P</tex><tex>(Q \times \Gamma^*)\rangle </tex>, где <br>* <tex>\Sigma</tex>: конечное множество входных символов.* <tex>Q</tex>: конечное множество состояний.* <tex>s</tex>: начальное состояние. * <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазин.* <tex>Z_0</tex>: начальный магазинный символ (маркер дна). Находится в магазине в начале работы автомата.* <tex>T</tex>: множество допускающих состояний.* <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>\gamma</tex>: цепочка магазинных символов, <i>замещающих</i> <tex>X</tex> на вершине магазина.}}{{Определение|definition =<b>Детерменированным автоматом [[Автоматы с магазинной памятью</b> называется |автомат с магазинной памятью]], для которого выполнены следующие условия:
#<tex>\mathcal8 q \in Q, a \in \Sigma \cup \{ \varepsilon \}, X \in \Gamma \Rightarrow \delta(q, a, X)</tex> имеет не более одного элемента {{---}} <tex> \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow Q \times \Gamma^*</tex>.
#Если <tex>\delta (q,a,X)</tex> непусто для некоторого <tex>a \in \Sigma</tex>, то <tex>\delta (q,\epsilon,X)</tex> должно быть пустым.
