57
правок
Изменения
→Детерминированный автомат с магазинной памятью
|definition=
Если для автомата с магазинной памятью выполняются следующие условия:
#<tex>\mathcal8 q \in Q, \mathcal8 c \in \Sigma, \mathcal8 X \chi \in \Gamma \Rightarrow \left | \delta(q, c, X\chi)\right | \le 1</tex>;#<tex>\delta(q,\varepsilon,X\chi) \ne 0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, X\chi) = \varnothing</tex>,
то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.
}}
Изменим автомат для языка <tex>0^n1^n</tex> из приведенного выше [[Автоматы с магазинной памятью#Пример|примера]] так, чтобы он стал детерминированным:
[[Изображение:DetPDAexample.png|thumb|left|Рис. 6. Детерминированный автомат с магазинной памятью для языка 0^n1^n]]
