142
правки
Изменения
Нет описания правки
==Недетерминированный автомат с магазинной памятью==
{{Определение
|definition= Автомат с магазинной памятью (автомат со стеком, pushdown automaton) {{---}} это набор <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> {{---}} стековый алфавит;
}}
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]
На рис. 1 изображен '''автомат с магазинной памятью (автомат со стеком, pushdown automaton).''' С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> {{---}} текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.
Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что [[Совпадение множества языков МП-автоматов и контекстно-свободных языков|недетерминированные автоматы со стеком эквивалентны по выразительной мощности контекстно свободным грамматикам.]] Если речь пойдет о [[Детерминированные автоматы с магазинной памятью|детерминированном автомате]], это будет указано отдельно. Заметим также, что [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами|детерминированные и недетерминированные автоматы со стеком неэквивалентны]].
<br style="clear:both" />
==Диаграммы переходов==
<div class="tleft" style="clear:none">[[Файл:Transition1.png|thumb|Рис. 2. Переход: с {{---}} символ, прочитанный с ленты; A {{---}} символ, вынутый из стека; <tex>\alpha</tex> {{---}} строка, помещаемая в стек.]]</div>
