Изменения

|definition= '''Автомат с магазинной памятью ''' (автомат со стеком, англ. ''pushdown automaton'') {{--- }} это набор A=<tex>A=\langle\Sigma,\Gamma,Q,s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow \cal P</tex><tex>(2^{Q \times \Gamma^*)}\rangle</tex>, где*<tex>\Sigma</tex> {{--- }} входной алфавит на ленте;,*<tex>\Gamma</tex> {{--- }} стековый алфавит;,*<tex>Q</tex> {{--- }} множество состояний автомата;,*<tex>s</tex> {{--- }} стартовое состояние автомата;,*<tex>T</tex> {{--- }} множество допускающих состояний автомата;,*<tex>z_0</tex> {{--- }} маркер дна стека;,*<tex>\delta</tex> {{--- }} функция переходов.

==Обозначения==[[Изображение:PDAsmall.jpg|left|Рис. 1. Автомат с магазинной памятью]]*'''Мгновенное описание:''' С ленты последовательно считываются символы входного алфавита (<tex>\langle q, \alpha, \gamma \ranglec_i</tex>, где {{---}} текущий считываемый символ). Символ <tex>qx</tex> --- текущее состояние, снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.  Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что [[Совпадение множества языков МП-автоматов и контекстно-свободных языков|недетерминированные автоматы со стеком эквивалентны по выразительной мощности контекстно свободным грамматикам.]] Если речь пойдет о [[Детерминированные автоматы с магазинной памятью|детерминированном автомате]], это будет указано отдельно. Заметим также, что [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами|детерминированные и недетерминированные автоматы со стеком неэквивалентны]].<br style="clear:both" /> ==Диаграммы переходов==<div class="tleft" style="clear:none">[[Файл:Transition1.png|400px|thumb|Рис. 2. Переход: с {{- остаток строки--}} символ, прочитанный с ленты; A {{---}} символ, вынутый из стека; <tex>\gammaalpha</tex> {{--- содержимое стека}} строка, помещаемая в стек.]]</div><div class="tleft" style="clear:none">[[Файл:Transition2.png|400px|thumb|Рис. 3. Переход по любому стековому символу, он же возвращается в стек.]]</div>*'''<div class="tleft" style="clear:none">[[Файл:Transition3.png|400px|thumb|Рис. 4. Переход по любому стековому символу, в стек кладется пустая строка.]]</div><br style="clear:both" />По соглашению маркер дна всегда находится на дне (за один шаг:''' исключением случая, когда автомат является [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|автоматом с допуском по пустому стеку]]). То есть, для <tex>\vdashforall q \in Q,\forall c \in \Sigma \cup \{\varepsilon\} \Rightarrow \delta(q, c, z_0) \ni \langle p, \alpha \rangle </tex>*'''Переход за ноль или более шагов:''' , где <tex>p \vdashin Q, \alpha \in \Gamma^*, \alpha = \alpha_1z_0</tex>. ==Основные определения==

|definition= Язык автомата с магазинной памятью '''Мгновенное описание''' (англ. ''instantaneous descriptions'') {{---}} это набор <tex>L(A)=\{\alpha \mid \langle sq, \alpha, z_0\gamma \rangle \vdash^* \langle t</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\varepsilonalpha</tex> {{---}} остаток строки, <tex>\gamma \rangle, t \in T\}</tex>{{---}} содержимое стека.

Если для автомата с магазинной памятью выполняются следующие условия:#'''Переход за один шаг''' (англ. ''the "goes-to" relation'') обозначается как <tex>\mathcal8 langle q , \in Qalpha, \mathcal8 c gamma \rangle \in vdash \Sigmalangle r, \mathcal8 X beta, \in xi \Gammarangle</tex> , где <tex>\left | alpha = c\deltabeta</tex> (qвозможно, <tex>c, X)=\right | \le 1varepsilon</tex>;#), <tex>\delta(qgamma = \chi\gamma',\varepsilonxi = \eta\gamma'</tex>,X) <tex>\ne 0 langle r, \Rightarrow eta \mathcal8 c rangle \in \Sigma : \delta(q, c, X\chi) = \varnothing</tex>,то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.