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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} ==Недетерминированный автомат с магазинной памятью== {{Определение |definition= А…»)
 
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
==Недетерминированный автомат с магазинной памятью==
 
==Недетерминированный автомат с магазинной памятью==
 +
По умолчанию будем считать автоматы с магазинной памятью недетерминированными. Если речь пойдет о детерминированном автомате, это будет указано отдельно.
 
{{Определение
 
{{Определение
|definition= Автомат с магазинной памятью --- это набор <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>, где
 
*<tex>\Sigma</tex> --- входной алфавит на ленте;
 
*<tex>\Sigma</tex> --- входной алфавит на ленте;
 
*<tex>\Gamma</tex> --- стековый алфавит;
 
*<tex>\Gamma</tex> --- стековый алфавит;
Строка 14: Строка 15:
  
 
==Обозначения==
 
==Обозначения==
 
+
*'''Мгновенное описание:''' <tex>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> --- текущее состояние, <tex>\alpha</tex> --- остаток строки, <tex>\gamma</tex> --- содержимое стека.
 +
*'''Переход за один шаг:''' <tex>\vdash</tex>
 +
*'''Переход за ноль или более шагов:''' <tex>\vdash^*</tex>
 +
{{Определение
 +
|definition= Язык автомата с магазинной памятью <tex>L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}</tex>
 +
}}
 
==Пример==
 
==Пример==
 +
Рассмотрим автомат с магазинной памятью для языка <tex>0^n1^n</tex>.
  
 
==Детерминированный автомат с магазинной памятью==
 
==Детерминированный автомат с магазинной памятью==

Версия 08:48, 20 октября 2010

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

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

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

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

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

Обозначения

  • Мгновенное описание: [math]\langle q, \alpha, \gamma \rangle[/math], где [math]q[/math] --- текущее состояние, [math]\alpha[/math] --- остаток строки, [math]\gamma[/math] --- содержимое стека.
  • Переход за один шаг: [math]\vdash[/math]
  • Переход за ноль или более шагов: [math]\vdash^*[/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].

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

Определение:
Если для автомата с магазинной памятью выполняются следующие условия:
  1. [math]\mathcal8 q \in Q, \mathcal8 c \in \Sigma, \mathcal8 X \in \Gamma[/math] [math]\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],
то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.