48
правок
Изменения
м
# : либо <tex>\alpha = \beta</tex>,# : либо <tex>\alpha = \delta X \alpha'</tex>, <tex>\beta = \delta Y \beta'</tex>, <tex>X \equiv Y</tex> и <tex>X \neq Y</tex>.
Нет описания правки
{{Определение
|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> нельзя ничего вывести).
}}
<tex>\alpha \equiv \beta</tex> если:
'''Свойства''' <tex>\equiv</tex>:
# <tex>\alpha\beta \equiv \alpha \Leftrightarrow \beta = \varepsilon</tex>.# <tex>\alpha \equiv \beta \Leftrightarrow \delta\alpha \equiv \delta\beta</tex>.# если Если <tex>\alpha \equiv \beta</tex> и <tex>\gamma \equiv \delta</tex>, тогда <tex>\alpha\gamma \equiv \beta\delta</tex>.# если Если <tex>\alpha \equiv \beta</tex> и <tex>\alpha \neq \beta</tex>, тогда <tex>\alpha\gamma \equiv \beta\delta</tex>.# если Если <tex>\alpha\gamma \equiv \beta\delta</tex> и <tex>|\alpha| = |\beta|</tex>, тогда <tex>\alpha \equiv \beta</tex>.
{{Определение
|definition=Отношение <tex>\equiv</tex> на множестве <tex>\Gamma</tex> является '''строгим''' (англ. ''strict''), если выполняются следующие условия:
# если Если <tex>X \equiv Y</tex>, <tex>(X, a) \rightarrow \alpha</tex> и <tex>(Y, a) \rightarrow \beta</tex>, тогда <tex>\alpha \equiv \beta</tex>.# если Если <tex>X \equiv Y</tex>, <tex>(X, a) \rightarrow \alpha</tex> и <tex>(Y, a) \rightarrow \alpha</tex>, тогда <tex>X = Y</tex>.
}}
|proof=
Пусть задан ДМП автомат в нормальной форме в виде четырех множеств <tex>Q, \Sigma, \Gamma, \Delta</tex>.
# Для двух состояний <tex>p, q \in Q</tex> и <tex>X \in \Gamma</tex> заведём новый символ стека <tex>[pXq]</tex>.# Для переходов сначала для данного <tex>a \in \Sigma</tex>:: #* если <tex>(p, a, X) \rightarrow (q, \varepsilon) \in \Delta</tex>, тогда <tex>([pXq], a) \rightarrow \varepsilon</tex>;: #* если <tex>(p, a, X) \rightarrow (q, Y) \in \Delta</tex>, тогда <tex>([pXr], a) \rightarrow [qYr]</tex> для всех <tex>r \in Q</tex>;: #* если <tex>(p, a, X) \rightarrow (q, YZ) \in \Delta</tex>, тогда <tex>([pXr], a) \rightarrow [qYp'][p'Zr]</tex> для всех <tex>r,p' \in Q</tex>.
# [pSq] считается <tex>\varepsilon</tex>-символом, если <tex>(p, \varepsilon, X) \rightarrow (q, \varepsilon) \in \Delta</tex>. Все <tex>\varepsilon</tex>-символы удаляются из правой части переходов, полученных в предыдущем пункте.
Полученный автомат с единственным состоянием также находится в нормальной форме. Детерминируем новый автомат, чтобы сохранить детерминированность.
