317
правок
Изменения
Нет описания правки
{{Определение
|definition =
'''Детерменированным Детерминированным автоматом с магазинной памятью''' (англ. ''deterministic pushdown automaton'') называется [[Автоматы с магазинной памятью|автомат с магазинной памятью]], для которого выполнены следующие условия:
#<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,\varepsilon,X)</tex> должно быть пустым.
==Пример==
Построим для языка:
# <tex> S \rightarrow 10H </tex># <tex> H \rightarrow 1H </tex># <tex> H \rightarrow 0H 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\}, \{Z_0,X\}, \{q,p\}, q, \{p\}, Z_0, \delta)</tex> с функией перехода <tex>\delta</tex>:
# <tex>\delta(q,0,Z_0)=(q,XZ_0)</tex>
