Изменения
→Основные определения
{{Определение
|definition=
'''Мгновенное описание ''' {{--- }} это набор <tex>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> {{--- }} текущее состояние, <tex>\alpha</tex> {{--- }} остаток строки, <tex>\gamma</tex> {{--- }} содержимое стека.
}}
{{Определение
|definition=
'''Переход за один шаг ''' обозначается как <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>.
}}
{{Определение
|definition= '''Язык автомата с магазинной памятью ''' <tex>L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}</tex>.
}}
==Пример недетерминированного МП-автомата==
На рис. 5 приведен пример недетерминированного автомата с магазинной памятью для языка <tex>0^n1^n</tex>.
