Автоматы с магазинной памятью — различия между версиями

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

Текущая версия на 19:28, 4 сентября 2022

Недетерминированный автомат с магазинной памятью

Определение:
Автомат с магазинной памятью (автомат со стеком, англ. pushdown automaton) — это набор [math]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[/math], где
  • [math]\Sigma[/math] — входной алфавит на ленте,
  • [math]\Gamma[/math] — стековый алфавит,
  • [math]Q[/math] — множество состояний автомата,
  • [math]s[/math] — стартовое состояние автомата,
  • [math]T[/math] — множество допускающих состояний автомата,
  • [math]z_0[/math] — маркер дна стека,
  • [math]\delta[/math] — функция переходов.


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

С ленты последовательно считываются символы входного алфавита ([math]c_i[/math] — текущий считываемый символ). Символ [math]x[/math] снимается с вершины стека. Вместо него помещается строка [math]\alpha[/math] таким образом, чтобы первый символ строки находился на вершине стека.

Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что недетерминированные автоматы со стеком эквивалентны по выразительной мощности контекстно свободным грамматикам. Если речь пойдет о детерминированном автомате, это будет указано отдельно. Заметим также, что детерминированные и недетерминированные автоматы со стеком неэквивалентны.

Диаграммы переходов

Рис. 2. Переход: с — символ, прочитанный с ленты; A — символ, вынутый из стека; [math]\alpha[/math] — строка, помещаемая в стек.
Рис. 3. Переход по любому стековому символу, он же возвращается в стек.
Рис. 4. Переход по любому стековому символу, в стек кладется пустая строка.


По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является автоматом с допуском по пустому стеку). То есть, для [math]\forall q \in Q,\forall c \in \Sigma \cup \{\varepsilon\} \Rightarrow \delta(q, c, z_0) \ni \langle p, \alpha \rangle [/math], где [math]p \in Q, \alpha \in \Gamma^*, \alpha = \alpha_1z_0[/math].

Основные определения

Определение:
Мгновенное описание (англ. instantaneous descriptions) — это набор [math]\langle q, \alpha, \gamma \rangle[/math], где [math]q[/math] — текущее состояние, [math]\alpha[/math] — остаток строки, [math]\gamma[/math] — содержимое стека.


Определение:
Переход за один шаг (англ. the "goes-to" relation) обозначается как [math]\langle q, \alpha, \gamma \rangle \vdash \langle r, \beta, \xi \rangle[/math], где [math]\alpha = c\beta[/math] (возможно, [math]c=\varepsilon[/math]), [math]\gamma = \chi\gamma', \xi = \eta\gamma'[/math], [math]\langle r, \eta \rangle \in \delta(q, c, \chi)[/math].


Определение:
Язык автомата с магазинной памятью (англ. language of a pushdown automaton) [math]L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}[/math].


Пример недетерминированного МП-автомата

Рис. 5. Недетерминированный МП-автомат для языка [math]0^n1^n[/math].

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)