57
правок
Изменения
Нет описания правки
{{В разработке}}
==Недетерминированный автомат с магазинной памятью==
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]На рис. 1 изображен автомат с магазинной памятью. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> --- текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека. По умолчанию будем считать автоматы с магазинной памятью недетерминированными. Если речь пойдет о детерминированном автомате, то это будет указано отдельно.
{{Определение
|definition= Автомат с магазинной памятью --- это набор A=<tex>\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>(Q \times \Gamma^*)\rangle</tex>, где
}}
==Диаграммы переходов==
<div class="tleft" style="clear:none">[[Файл:Transition1.png|thumb|Рис. 2. Переход: с - символ, прочитанный с ленты; A - символ, вынутый из стека; <tex>\alpha</tex> - строка, помещаемая в стек]]</div><div class="tleft" style="clear:none">[[Файл:Transition2.png|thumb|Рис. 3. Переход по любому стековому символу, он же возвращается в стек]]</div><div class="tleft" style="clear:none">[[Файл:Transition3.png|thumb|Рис. 4. Переход по любому стековому символу, в стек кладется пустая строка]]</div>
<br style="clear:both" />
По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является автоматом с допуском по пустому стеку). То есть, для <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>0^n1^n</tex>.
[[Изображение:PDAexample.png|200px|thumb|center|Рис. 5. Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>]]
==Детерминированный автомат с магазинной памятью==
