Изменения

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

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

685 байт убрано, 00:18, 7 декабря 2016
Нет описания правки
{{Определение
|definition =
<b> Автоматом '''Детерминированным автоматом с магазинной памятью </b> называется набор <tex> A = \langle\Sigma,Q,s\in Q, \Gamma, Z_0 \in \Gamma, T \subset Q, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow \cal P</tex><tex>''' (Q \times \Gamma^*)\rangle </tex>, где <br>* <tex>\Sigma</tex>: конечное множество входных символов.* <tex>Q</tex>: конечное множество состояний.* <tex>s</tex>: начальное состояние. * <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазинангл.* <tex>Z_0</tex>: начальный магазинный символ (маркер дна''deterministic pushdown automaton''). Находится в магазине в начале работы автомата.* <tex>T</tex>: множество допускающих состояний.* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где** <tex>q</tex>: текущее состояние из Q.** <tex>a</tex>: входной символ или <tex>\epsilon</tex>.** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>.** <tex>p</tex>: новое состояние из Q.** <tex>\gamma</tex>: цепочка магазинных символов, <i>замещающих</i> <tex>X</tex> на вершине магазина.}}{{Определение|definition =<b>Детерменированным автоматом называется [[Автоматы с магазинной памятью</b> называется |автомат с магазинной памятью]], для которого выполнены следующие условия:
#<tex>\mathcal8 q \in Q, a \in \Sigma \cup \{ \varepsilon \}, X \in \Gamma \Rightarrow \delta(q, a, X)</tex> имеет не более одного элемента {{---}} <tex> \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow Q \times \Gamma^*</tex>.
#Если <tex>\delta (q,a,X)</tex> непусто для некоторого <tex>a \in \Sigma</tex>, то <tex>\delta (q,\epsilonvarepsilon,X)</tex> должно быть пустым.
}}
Будем обозначать переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_2,a_2,X_2)</tex> как <tex>(q_1,a_1,X_1)\vdash(q_2,a_2,X_2)</tex>. Переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_{p+1},a_{p+1},X_{p+1})</tex> через <tex>P</tex> промежуточных состояний обозначаем <tex>(q_1,a_1,X_1)\vdash^*_P(q_{p+1},a_{p+1},X_{p+1})</tex>.
==Пример==
Автомат Построим для языка:# <tex> S \rightarrow 1H </tex># <tex> H \rightarrow 0F </tex># <tex> H \rightarrow \varepsilon </tex># <tex> F \rightarrow 0F </tex># <tex> F \rightarrow 1F </tex># <tex> F \rightarrow \varepsilon </tex>автомат <tex>A=(\{0,1\},\{qZ_0,pX\},q, \{Z_0q,Xp\}, Z_0q,\{p\}, Z_0, \delta)</tex> с функией перехода <tex>\delta</tex>:
# <tex>\delta(q,0,Z_0)=(q,XZ_0)</tex>
# <tex>\delta(q,0,X)=(q,XX)</tex># <tex>\delta(q,1,X)=(q,X)</tex>
# <tex>\delta(q,1,Z_0)=(p,Z_0)</tex>
# <tex>\delta(p,0,Z_0)=(p,XZ_0)</tex>
# <tex>\delta(p,0,X)=(p,XX)</tex># <tex>\delta(p,1,X)=(p,X)</tex> <br> <br>
[[Файл:Пример_мп-автомата.png]]
 
== См. также ==
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
* [[ДМП-автоматы и неоднозначность]]
 
== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528с. : ISBN 978-5-8459-1347-0 (рус.)
 
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: МП-автоматы]]
Zernov
317
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/13821...57086»

Навигация