Редактирование: Автоматы с магазинной памятью

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
==Недетерминированный автомат с магазинной памятью==
 
==Недетерминированный автомат с магазинной памятью==
 +
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]
 +
На рис. 1 изображен '''автомат с магазинной памятью (автомат со стеком, pushdown automaton).''' С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> {{---}} текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.
 +
 +
Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что [[Совпадение множества языков МП-автоматов и контекстно-свободных языков|недетерминированные автоматы со стеком эквивалентны по выразительной мощности контекстно свободным грамматикам.]] Если речь пойдет о [[Автоматы с магазинной памятью#Детерминированный автомат с магазинной памятью|детерминированном автомате]], это будет указано отдельно. Заметим также, что [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами|детерминированные и недетерминированные автоматы со стеком неэквивалентны]].
 +
<br style="clear:both" />
 
{{Определение
 
{{Определение
|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>, где
+
|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>(Q \times \Gamma^*)\rangle</tex>, где
*<tex>\Sigma</tex> {{---}} входной алфавит на ленте,
+
*<tex>\Sigma</tex> {{---}} входной алфавит на ленте;
*<tex>\Gamma</tex> {{---}} стековый алфавит,
+
*<tex>\Gamma</tex> {{---}} стековый алфавит;
*<tex>Q</tex> {{---}} множество состояний автомата,
+
*<tex>Q</tex> {{---}} множество состояний автомата;
*<tex>s</tex> {{---}} стартовое состояние автомата,
+
*<tex>s</tex> {{---}} стартовое состояние автомата;
*<tex>T</tex> {{---}} множество допускающих состояний автомата,
+
*<tex>T</tex> {{---}} множество допускающих состояний автомата;
*<tex>z_0</tex> {{---}} маркер дна стека,
+
*<tex>z_0</tex> {{---}} маркер дна стека;
 
*<tex>\delta</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">[[Файл:Transition1.png|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">[[Файл:Transition2.png|thumb|Рис. 3. Переход по любому стековому символу, он же возвращается в стек.]]</div>
<div class="tleft" style="clear:none">[[Файл:Transition3.png|400px|thumb|Рис. 4. Переход по любому стековому символу, в стек кладется пустая строка.]]</div>
+
<div class="tleft" style="clear:none">[[Файл:Transition3.png|thumb|Рис. 4. Переход по любому стековому символу, в стек кладется пустая строка.]]</div>
 
<br style="clear:both" />
 
<br style="clear:both" />
По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|автоматом с допуском по пустому стеку]]). То есть, для <tex>\forall q \in Q,\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>.
+
По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|автоматом с допуском по пустому стеку]]). То есть, для <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>.
  
 
==Основные определения==
 
==Основные определения==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Мгновенное описание''' (англ. ''instantaneous descriptions'') {{---}} это набор <tex>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} остаток строки, <tex>\gamma</tex> {{---}} содержимое стека.
+
'''Мгновенное описание''' {{---}} это набор <tex>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} остаток строки, <tex>\gamma</tex> {{---}} содержимое стека.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|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>.
+
'''Переход за один шаг''' обозначается как <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>.
+
|definition= '''Язык автомата с магазинной памятью''' <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" />
+
На рис. 5 приведен пример недетерминированного автомата с магазинной памятью для языка <tex>0^n1^n</tex>.
 +
[[Изображение:PDAexample.png|200px|thumb|left|Рис. 5. Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>.]]<br style="clear:both" />
  
== См. также ==
+
==Детерминированный автомат с магазинной памятью==
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
+
{{Определение
* [[ДМП-автоматы и неоднозначность]]
+
|definition=
 
+
Если для автомата с магазинной памятью выполняются следующие условия:
== Источники информации ==
+
#<tex>\mathcal8 q \in Q, \mathcal8 c \in \Sigma \cup \{ \varepsilon \}, \mathcal8 \chi \in \Gamma \Rightarrow \left | \delta(q, c, \chi)\right | \le 1</tex>;
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)
+
#<tex>\delta(q,\varepsilon,\chi) \ne 0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, \chi) = \varnothing</tex>,
 +
то поведение автомата всегда определено однозначно, и он называется '''детерминированным автоматом с магазинной памятью'''.
 +
}}
 +
Изменим автомат для языка <tex>0^n1^n</tex> из приведенного выше [[Автоматы с магазинной памятью#Пример недетерминированного МП-автомата|примера]] так, чтобы он стал детерминированным:
 +
[[Изображение:DetPDAexample.png|thumb|200px|left|Рис. 6. Детерминированный автомат с магазинной памятью для языка <tex>0^n1^n</tex>.]]<br style="clear:both" />
  
[[Категория: Теория формальных языков]]
+
==Источники==
[[Категория: Контекстно-свободные грамматики]]
+
*Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.. : Пер. с англ. — М. : Издательский дом "Вильямс", 2002.
[[Категория: МП-автоматы]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: