Изменения

Определим <tex>P='''Детерминированным автоматом с магазинной памятью''' (Q,\Sigma,\Gamma,\delta,q_0,Z_0,Fангл. ''deterministic pushdown automaton'')</tex> как <b>называется [[Автоматы с магазинной памятью|автомат с магазинной (стековой) памятью</b>]], где <br>для которого выполнены следующие условия:* #<tex>\mathcal8 q \in Q</tex>: конечное множество состояний.* <tex>, a \in \Sigma</tex>: конечное множество входных символов.* <tex>\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)=(p,\gamma)</tex>, где** <tex>q</tex>: текущее состояние из Q.** непусто для некоторого <tex>a</tex>: входной символ или <tex>\epsilonin \Sigma</tex>.** <tex>X</tex>: магазинный символ из , то <tex>\Gamma</tex>.** <tex>p</tex>: новое состояние из Q.** <tex>delta (q,\gamma</tex>: цепочка магазинных символовvarepsilon, <i>замещающих</i> <tex>X</tex> на вершине магазина.* <tex>q_0</tex>: начальное состояние. * <tex>Z_0</tex>: начальный магазинный символ (маркер дна). Находится в магазине в начале работы автомата.* <tex>F</tex>: множество допускающих состоянийдолжно быть пустым.

Автомат Построим для языка:# <tex>PS \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=(\{q0,p1\},\{0Z_0,1X\},\{Z_0q,Xp\},\delta,q,Z_0,\{p\}, Z_0, \delta)</tex> с функией перехода <tex>\delta</tex>:

# <tex>\delta(q,0,X)=(q,XX)</tex># <tex>\delta(q,1,X)=(q,X)</tex># <tex>\delta(q,01,Z_0)=(p,Z_0)</tex>

# <tex>\delta(p,0,X)=(p,XX)</tex># <tex>\delta(p,1,X)=(p,X)</tex> <br> <br>[[Файл:Пример_мп-автомата.png]] == См. также ==* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МПавтоматами]]* [[ДМП-автоматавтоматы и неоднозначность]] == Источники информации ==* ''Хопкрофт Д.png, Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528с. : ISBN 978-5-8459-1347-0 (рус.) [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: МП-автоматы]]