48
правок
Изменения
м
Детерминированный стековый автомат
Опеределение Определение конфигураций автомата с единственным состоянием расшириряется расширяется на наборы из последовательностей символов стека <tex>\{ \alpha_1, \ldots , \alpha_n \}</tex>, которые записываются в виде суммы <tex>\alpha_1 + \ldots + \alpha_n</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| \le leqslant 2</tex>, где <tex>\alpha \in \Gamma^*</tex> {{---}} последовательность стековых символов, <tex>S \in \Gamma</tex>.;# если <tex>(p, \epsilonvarepsilon, S) \rightarrow (q, \alpha) \in \Delta</tex>, то <tex>\alpha = \epsilonvarepsilon</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, \epsilonvarepsilon) \}</tex>.
}}
и переходы имеют следующий вид:
: <tex>(p, a, X) \rightarrow (p, X)</tex>
: <tex>(p, b, X) \rightarrow (p, \epsilonvarepsilon)</tex>
: <tex>(p, c, X) \rightarrow (p, X)</tex>
: <tex>(r, \epsilonvarepsilon, X) \rightarrow (p, \epsilonvarepsilon)</tex>: <tex>(p, a, Y) \rightarrow (p, \epsilonvarepsilon)</tex>: <tex>(p, b, Y) \rightarrow (r, \epsilonvarepsilon)</tex>
: <tex>(p, c, Y) \rightarrow (p, YY)</tex>
: <tex>(r, \epsilonvarepsilon, Y) \rightarrow (r, \epsilonvarepsilon)</tex>Данный автомат будет являтся являться [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|ДМП автоматом с допуском по пустому стеку]] в нормальной форме.
== Автомат с единственным состоянием ==
{{Определение
|definition=Множество слов выводиых выводимых из конфигурации <tex>L(\alpha) = \{ \omega \in \Sigma^* : (\alpha, \omega) \rightarrow \epsilon varepsilon \}</tex>.
}}
{{Определение
|definition=Автомат с единственным состоянием находится в '''нормальной форме''', если все его переходы удовлетворяют условию:
: если <tex>(S, a) \rightarrow \alpha \in \Delta</tex>, тогда <tex>|\alpha| \le leqslant 2</tex> и <tex>L(\alpha) \neq \emptyset</tex>.
}}
Автомат с единственным состоянием можно сделать детерминированным, наложив следующее требование на переходы:
: если <tex>(S, a) \rightarrow \alpha \in \Delta</tex> и <tex>(S, a) \rightarrow \beta \in \Delta</tex>, тогда <tex>\alpha = \beta</tex>.
Детерминированный автомат с единственным состоянием соответствует по мощности "простым грамматикам".
{{Определение
|definition='''Простая грамматика''' (англ. ''Simple Grammar'') {{---}} такая грамматика, где все продукции имеют вид:
: <tex>A \rightarrow \alpha B_1 B_2 \ldots B_n</tex>, где <tex>\alpha</tex> {{---}} терминал, а все <tex>B_i, i = 1 \ldots n</tex> {{---}} нетерминалы, и существует только одна продукция с парой <tex>\langle A, \alpha \rangle</tex>.
}}
Однако, множество языков допускаемых детерминированным автоматом с единственным состоянием является строгим подможеством подмножеством языков [[Детерминированные автоматы с магазинной памятью|ДМП автоматов]], поэтому больший интерес представляют ''строгие'' автоматы с единственным состоянием.
Для этого вводится отношение эквивалентности <tex>\equiv</tex> на множестве <tex>\Gamma</tex>, заданное разбиением <tex>\Gamma</tex> на непересекающиеся подмоножестваподмножества.
'''Пример 1'''
: <tex>\Sigma = \{a, b\}</tex>
: <tex>\Gamma = \{A, C, X, Y\}</tex>
Переходы:
: <tex>(X, a) \rightarrow YX</tex>
: <tex>(X, b) \rightarrow \epsilonvarepsilon</tex>
: <tex>(Y, b) \rightarrow X</tex>
: <tex>(A, a) \rightarrow C</tex>
: <tex>(A, b) \rightarrow \epsilonvarepsilon</tex>
: <tex>(C, b) \rightarrow AA</tex>
Разбиение <tex>\Gamma</tex> имеет вид <tex>\{\{A\}, \{C\}, \{X\}, \{Y\}\}</tex>.
Такой автомат будет детерминированным.
Переходы:
: <tex>(X, a) \rightarrow X</tex>
: <tex>(X, b) \rightarrow \epsilonvarepsilon</tex>
: <tex>(X, c) \rightarrow X</tex>
: <tex>(Y, a) \rightarrow \epsilonvarepsilon</tex>
: <tex>(Y, c) \rightarrow YY</tex>
: <tex>(Z, b) \rightarrow \epsilonvarepsilon</tex>
: <tex>(Z, c) \rightarrow Z</tex>
: <tex>(Z, c) \rightarrow YZ</tex>
'''Свойства''' <tex>\equiv</tex>:
# <tex>\alpha\beta \equiv \alpha \Leftrightarrow \beta = \epsilonvarepsilon</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>
{{Определение
|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>
{{Определение
|definition=Автомат с единственным состоянием с заданным разбиением <tex>\Gamma</tex> является '''строгим'''(англ. ''strict''), если отношение <tex>\equiv</tex> строгое на множестве <tex>\Gamma</tex>.
}}
Две суммы конфигураций считаются эквивалентными (записывается через <tex>=</tex>), если они представляют из себя собой один и тот же набор.
Язык суммы конфигураций определяется {{---}} <tex>L(\alpha_1 + \ldots + \alpha_n) = \bigcup\limits_{i = 1}^{n}L(\alpha_i) : i = 1 \ldots n\}</tex>
{{Определение
|definition=Сумма конфигураций <tex>\beta_1 + \ldots + \beta_n</tex> называется '''допустимой''' (англ. ''admissible''), если <tex>\beta_i \equiv \beta_j</tex> для всех елементов элементов суммы, и <tex>\beta_i \neq \beta_j</tex> при <tex>i \neq j</tex>.
}}
Таким образом <tex>\emptyset</tex> {{---}} тоже допустимо.
<tex>(X, a) \rightarrow \alpha_1, \ldots , (X, a) \rightarrow \alpha_n</tex> из <tex>\Delta</tex>
заменяются на один переход <tex>(X, a) \rightarrow \alpha_1 + \ldots + \alpha_n</tex>.
Таким образом для каждого <tex>X \in \Gamma</tex> и <tex>a \in \Sigma</tex> будет уникальный переход <tex>(X, a) \rightarrow \sum{}{}{\alpha_i}</tex> из <tex>\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, \epsilonvarepsilon) \in \Delta</tex>, тогда <tex>([pXq], a) \rightarrow \epsilonvarepsilon</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>\epsilonvarepsilon</tex>-символом, если <tex>(p, \epsilonvarepsilon, X) \rightarrow (q, \epsilonvarepsilon) \in \Delta</tex>. Все <tex>\epsilonvarepsilon</tex>-символы удаляются из правой части переходов, полученных в предыдущем пункте.
Полученный автомат с единственным состоянием также находится в нормальной форме. Детерминируем новый автомат, чтобы сохранить детерминированность.
Таким образом каждая конфигурация вида <tex>pX_1X_2 \ldots X_n</tex> из исходного автомата была трансформирована в <tex>sum(p\alpha) = \sum_sum\limits_{p_i \in Q}{[p X_1 p_1][p_1 X_2 p_2] \ldots [p_{n-1}X_n p_n]}</tex> и <tex>L(p\alpha) = L(sum(p\alpha))</tex>.
}}
Применим алгоритм к самому первому примеру и получим следующее:
: <tex>(X, a) \rightarrow X</tex>
: <tex>(Y, a) \rightarrow \epsilonvarepsilon</tex>
: <tex>(Z, a) \rightarrow \emptyset</tex>
: <tex>(X, b) \rightarrow \epsilonvarepsilon</tex>
: <tex>(Y, b) \rightarrow \emptyset</tex>
: <tex>(Z, b) \rightarrow \epsilonvarepsilon</tex>
: <tex>(X, c) \rightarrow X</tex>
: <tex>(Y, c) \rightarrow YY</tex>
: <tex>Z = [pYr]</tex>
== Примение Применение ==Существует задача об определении эквивалентности двух [[Детерминированные автоматы с магазинной памятью|ДМП автоматов]] (два ДМП автомата <tex>M_1</tex> и <tex>М_2M_2</tex> эквивалетныэквивалентны, если <tex>L(M_1) = L(M_2)</tex>).Для этого автоматы переводятся в нормальную форму, а потом переводятся затем в автоматы с единственным состоянием, для которых эта задача разрешима, следовательно разрешима и изначальная задача.
== См. также ==
