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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Недетерминированный автомат с магазинной памятью)
Строка 2: Строка 2:
 
==Недетерминированный автомат с магазинной памятью==
 
==Недетерминированный автомат с магазинной памятью==
 
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]
 
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]
На рис. 1 изображен автомат с магазинной памятью. С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> --- текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.  
+
На рис. 1 изображен '''автомат с магазинной памятью (автомат со стеком, push down automaton).''' С ленты последовательно считываются символы входного алфавита (<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>, где
+
|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>\Sigma</tex> --- входной алфавит на ленте;
 
*<tex>\Gamma</tex> --- стековый алфавит;
 
*<tex>\Gamma</tex> --- стековый алфавит;
Строка 15: Строка 16:
 
*<tex>\delta</tex> --- функция переходов.
 
*<tex>\delta</tex> --- функция переходов.
 
}}
 
}}
 +
 
==Диаграммы переходов==
 
==Диаграммы переходов==
 
<div class="tleft" style="clear:none">[[Файл:Transition1.png|thumb|Рис. 2. Переход: с - символ, прочитанный с ленты; A - символ, вынутый из стека; <tex>\alpha</tex> - строка, помещаемая в стек]]</div>
 
<div class="tleft" style="clear:none">[[Файл:Transition1.png|thumb|Рис. 2. Переход: с - символ, прочитанный с ленты; A - символ, вынутый из стека; <tex>\alpha</tex> - строка, помещаемая в стек]]</div>

Версия 23:48, 27 октября 2010

Эта статья находится в разработке!

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

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

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

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


Определение:
Автомат с магазинной памятью (автомат со стеком, push down automaton) --- это набор A=[math]\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[/math][math](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] --- функция переходов.


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

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


По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является автоматом с допуском по пустому стеку). То есть, для [math]\mathcal8 q \in Q,\mathcal8 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]

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

  • Мгновенное описание: [math]\langle q, \alpha, \gamma \rangle[/math], где [math]q[/math] --- текущее состояние, [math]\alpha[/math] --- остаток строки, [math]\gamma[/math] --- содержимое стека.
  • Переход за один шаг обозначается как [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]
Определение:
Язык автомата с магазинной памятью [math]L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}[/math]

Пример

Рассмотрим недетерминированный автомат с магазинной памятью для языка [math]0^n1^n[/math].

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

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

Определение:
Если для автомата с магазинной памятью выполняются следующие условия:
  1. [math]\mathcal8 q \in Q, \mathcal8 c \in \Sigma, \mathcal8 X \in \Gamma \Rightarrow \left | \delta(q, c, X)\right | \le 1[/math];
  2. [math]\delta(q,\varepsilon,X) \ne 0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, X) = \varnothing[/math],
то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.