57
правок
Изменения
Нет описания правки
}}
==Диаграмма переходов==
По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является автоматом с допуском по пустому стеку).То есть, для <tex>\mathcal8 q \in Q,\mathcal8 c \in \Sigma \cup \varepsilon \Rightarrow \delta(q, c, z_0) \ni \langle p, \alpha \rangle </tex>, где <tex>p \in Q, \alpha \in \Gamma^*, \alpha = \alpha_1z_0</tex>
==Основные определения==
*'''Мгновенное описание:''' <tex>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> --- текущее состояние, <tex>\alpha</tex> --- остаток строки, <tex>\gamma</tex> --- содержимое стека.
*'''Переход за один шаг''' обозначается как <tex>\langle q, \alpha, \gamma \rangle \vdash \langle r, \beta, \xi \rangle</tex> и означает, что если где <tex>\alpha = c\beta</tex> (возможно,<tex>c=\varepsilon</tex>), <tex>\gamma = \chi\gamma', \xi = \eta\gamma'</tex>, то <tex>\langle r, \eta \rangle \in \delta(q, c, \chi)</tex>*'''Переход за ноль или более шагов:''' <tex>\vdash^*</tex>
{{Определение
|definition= Язык автомата с магазинной памятью <tex>L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}</tex>
|definition=
Если для автомата с магазинной памятью выполняются следующие условия:
#<tex>\mathcal8 q \in Q, \mathcal8 c \in \Sigma, \mathcal8 X \in \Gamma</tex> <tex>\Rightarrow \left | \delta(q, c, X)\right | \le 1</tex>;
#<tex>\delta(q,\varepsilon,X) \ne 0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, X) = \varnothing</tex>,
то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.
}}
