Изменения

Перейти к: навигация, поиск

Автоматы с магазинной памятью

367 байт убрано, 11:41, 27 мая 2019
м
Диаграммы переходов
{{В разработке}}
==Недетерминированный автомат с магазинной памятью==
{{Определение|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 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> {{---}} функция переходов.}} [[Изображение:PDAPDAsmall.png|thumbjpg|left|Рис. 1. Автомат с магазинной памятью]]На рис. 1 изображен '''автомат с магазинной памятью (автомат со стеком, push down automaton).''' С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> {{--- }} текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.
Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что [[Совпадение множества языков МП-автоматов и контекстно-свободных языков|недетерминированные автоматы со стеком эквиваленты эквивалентны по выразительной мощности контекстно свободным грамматикам.]] Если речь пойдет о [[Автоматы с магазинной памятью#Детерминированный автомат Детерминированные автоматы с магазинной памятью|детерминированном автомате]], это будет указано отдельно. Заметим также, что [[Детерминированные автоматы с магазинной памятьюНесовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами|детерминированные и недетерминированные автоматы со стеком неэквивалентны.]].<br style="clear:both" />
{{Определение
|definition= Автомат с магазинной памятью (автомат со стеком, push down automaton) --- это набор 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>, где
*<tex>\Sigma</tex> --- входной алфавит на ленте;
*<tex>\Gamma</tex> --- стековый алфавит;
*<tex>Q</tex> --- множество состояний автомата;
*<tex>s</tex> --- стартовое состояние автомата;
*<tex>T</tex> --- множество допускающих состояний автомата;
*<tex>z_0</tex> --- маркер дна стека;
*<tex>\delta</tex> --- функция переходов.
}}
==Диаграммы переходов==
<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>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> {{--- }} текущее состояние, <tex>\alpha</tex> {{--- }} остаток строки, <tex>\gamma</tex> {{--- }} содержимое стека.
}}
{{Определение
|definition=
'''Переход за один шаг ''' (англ. ''the "goes-to" relation'') обозначается как <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= '''Язык автомата с магазинной памятью ''' (англ. ''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>.
}}
 ==Примернедетерминированного МП-автомата==На рис. 5 приведен пример недетерминированного автомата с магазинной памятью для языка <tex>0^n1^n</tex>.[[Изображение:PDAexample.png|200px300px|thumb|left|Рис. 5. Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>.]]<br style="clear:both" /> == См. также ==Детерминированный автомат * [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]* [[ДМП-автоматы и неоднозначность]] =={{Определение|definitionИсточники информации ==Если для автомата с магазинной памятью выполняются следующие условия:#<tex>\mathcal8 q \in Q* ''Хопкрофт Д., \mathcal8 c \in \SigmaМотвани Р., \mathcal8 \chi \in \Gamma \Rightarrow \left | \delta(qУльман Д.'' {{---}} '''Введение в теорию автоматов, cязыков и вычислений''', \chi)\right | \le 1</tex>;#<tex>\delta(q2-е изд. : Пер. с англ. — Москва,\varepsilonИздательский дом «Вильямс»,\chi) \ne 2008. — 528 с. : ISBN 978-5-8459-1347-0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, \chiрус.) = \varnothing</tex>,то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.}}[[Категория: Теория формальных языков]]Изменим автомат для языка <tex>0^n1^n</tex> из приведенного выше [[Автоматы с магазинной памятью#Пример|примераКатегория: Контекстно-свободные грамматики]] так, чтобы он стал детерминированным:[[ИзображениеКатегория:DetPDAexample.png|thumb|left|Рис. 6. Детерминированный автомат с магазинной памятью для языка 0^n1^nМП-автоматы]]
4
правки

Навигация