Просмотр исходного текста страницы Нормальная форма ДМП-автомата

== Определение ==
{{Определение
|definition=ДМП в '''нормальной форме''' (англ. ''Normal Form'') называется такой [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|детерминированный автомат с магазинной памятью]] <tex>M</tex>, представленный конечным набором состояний <tex>Q</tex>, входным алфавитом на ленте <tex>\Sigma</tex>, стековым алфавитом <tex>\Gamma</tex> и множеством переходов <tex>\Delta</tex>, который удовлетворяет следующим условиям:
# Если <tex>(p, a, S) \rightarrow (q, \alpha) \in \Delta</tex>, то <tex>|\alpha| \leqslant 2</tex>, где <tex>\alpha \in \Gamma^*</tex> {{---}} последовательность стековых символов, <tex>S \in \Gamma</tex>.
# Если <tex>(p, \varepsilon, S) \rightarrow (q, \alpha) \in \Delta</tex>, то <tex>\alpha = \varepsilon</tex>.
# <tex>\Delta</tex> не содержит бесполезных переходов (переход <tex>(p, a, S) \rightarrow (q, \alpha)</tex> считается бесполезным, если <tex>L(q, \alpha) = \emptyset</tex>, то есть из конфигурации <tex>(q, \alpha)</tex> нельзя ничего вывести).
}}

{{Определение
|definition=Множество слов выводимых из конфигурации <tex>L(p, \sigma) = \{ \omega \in \Sigma^* : \exists q \in Q (p, \omega, \sigma) \rightarrow (q, \varepsilon) \}</tex>.
}}

'''Замечание:''' здесь и далее речь идёт о [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|ДМП с допуском по пустому стеку]].