1632
правки
Изменения
м
{{В разработке}}
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]
На рис. 1 изображен автомат с магазинной памятью. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> --- текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</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>0^n1^n</tex>.
[[Изображение:PDAexample.png|200px|thumb|center|Рис. 5. Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>]]
==Детерминированный автомат с магазинной памятью==
Если для автомата с магазинной памятью выполняются следующие условия:#'''Переход за один шаг''' (англ. ''the "goes-to" relation'') обозначается как <tex>\mathcal8 langle q , \in Qalpha, \mathcal8 c gamma \rangle \in vdash \Sigmalangle r, \mathcal8 X beta, \in xi \Gamma rangle</tex>, где <tex>\Rightarrow alpha = c\left | \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>,то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.
rollbackEdits.php mass rollback
==Недетерминированный автомат с магазинной памятью==
{{Определение
|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>c_i</tex> {{---}} текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.
Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что [[Совпадение множества языков МП-автоматов и контекстно-свободных языков|недетерминированные автоматы со стеком эквивалентны по выразительной мощности контекстно свободным грамматикам.]] Если речь пойдет о [[Детерминированные автоматы с магазинной памятью|детерминированном автомате]], это будет указано отдельно. Заметим также, что [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами|детерминированные и недетерминированные автоматы со стеком неэквивалентны]].
<br style="clear:both" />
==Диаграммы переходов==
<div class="tleft" style="clear:none">[[Файл:Transition1.png|400px|thumb|Рис. 2. Переход: с {{--- }} символ, прочитанный с ленты; A {{-- -}} символ, вынутый из стека; <tex>\alpha</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>\mathcal8 forall q \in Q,\mathcal8 forall 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>.
==Основные определения==
{{Определение
|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>{{---}} содержимое стека.
}}
{{Определение
|definition=
}}
{{Определение
|definition= '''Язык автомата с магазинной памятью''' (англ. ''language of a pushdown automaton'') <tex>L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}</tex>.
}}
==Пример недетерминированного МП-автомата==
[[Изображение:PDAexample.png|300px|thumb|left|Рис. 5. Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>.]]<br style="clear:both" />
== См. также ==
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
* [[ДМП-автоматы и неоднозначность]]
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: МП-автоматы]]
