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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Диаграмма переходов)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
==Недетерминированный автомат с магазинной памятью==
 
==Недетерминированный автомат с магазинной памятью==
По умолчанию будем считать автоматы с магазинной памятью недетерминированными. Если речь пойдет о детерминированном автомате, то это будет указано отдельно.
+
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]
 +
На рис. 1 изображен автомат с магазинной памятью. С ленты последовательно считываются символы входного алфавита (<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= Автомат с магазинной памятью --- это набор 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>, где
Строка 13: Строка 16:
 
}}
 
}}
 
==Диаграммы переходов==
 
==Диаграммы переходов==
<div class="tleft" style="clear:none">[[Файл:Transition1.png|thumb|Переход: с - символ, прочитанный с ленты; 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|thumb|Переход по любому стековому символу, он же возвращается в стек]]</div>
+
<div class="tleft" style="clear:none">[[Файл:Transition2.png|thumb|Рис. 3. Переход по любому стековому символу, он же возвращается в стек]]</div>
<div class="tleft" style="clear:none">[[Файл:Transition3.png|thumb|Переход по любому стековому символу, в стек кладется пустая строка]]</div>
+
<div class="tleft" style="clear:none">[[Файл:Transition3.png|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>\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>
Строка 27: Строка 30:
 
==Пример==
 
==Пример==
 
Рассмотрим недетерминированный автомат с магазинной памятью для языка <tex>0^n1^n</tex>.
 
Рассмотрим недетерминированный автомат с магазинной памятью для языка <tex>0^n1^n</tex>.
[[Изображение:PDAexample.png|200px|thumb|center|Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>]]
+
[[Изображение:PDAexample.png|200px|thumb|center|Рис. 5. Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>]]
  
 
==Детерминированный автомат с магазинной памятью==
 
==Детерминированный автомат с магазинной памятью==

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

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

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

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

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

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

Определение:
Автомат с магазинной памятью --- это набор 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],
то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.