Определение
| Определение: |
ДМП в нормальной форме (англ. Normal Form) называется такой детерминированный автомат с магазинной памятью [math]M[/math], представленный конечным набором состояний [math]Q[/math], входным алфавитом на ленте [math]\Sigma[/math], стековым алфавитом [math]\Gamma[/math] и множеством переходов [math]\Delta[/math], который удовлетворяет следующим условиям:
- Если [math](p, a, S) \rightarrow (q, \alpha) \in \Delta[/math], то [math]|\alpha| \leqslant 2[/math], где [math]\alpha \in \Gamma^*[/math] — последовательность стековых символов, [math]S \in \Gamma[/math].
- Если [math](p, \varepsilon, S) \rightarrow (q, \alpha) \in \Delta[/math], то [math]\alpha = \varepsilon[/math].
- [math]\Delta[/math] не содержит бесполезных переходов (переход [math](p, a, S) \rightarrow (q, \alpha)[/math] считается бесполезным, если [math]L(q, \alpha) = \emptyset[/math], то есть из конфигурации [math](q, \alpha)[/math] нельзя ничего вывести).
|
| Определение: |
| Множество слов выводимых из конфигурации [math]L(p, \sigma) = \{ \omega \in \Sigma^* : \exists q \in Q (p, \omega, \sigma) \rightarrow (q, \varepsilon) \}[/math]. |
Замечание: здесь и далее речь идёт о ДМП с допуском по пустому стеку.
Пример
Пусть
- [math]Q = \{p, r\}[/math]
- [math]\Sigma = \{a, b, c\}[/math]
- [math]\Gamma = \{X, Y\}[/math]
- [math](p, X)[/math] — стартовая конфигурация
и переходы имеют следующий вид:
- [math](p, a, X) \rightarrow (p, X)[/math]
- [math](p, b, X) \rightarrow (p, \varepsilon)[/math]
- [math](p, c, X) \rightarrow (p, X)[/math]
- [math](r, \varepsilon, X) \rightarrow (p, \varepsilon)[/math]
- [math](p, a, Y) \rightarrow (p, \varepsilon)[/math]
- [math](p, b, Y) \rightarrow (r, \varepsilon)[/math]
- [math](p, c, Y) \rightarrow (p, YY)[/math]
- [math](r, \varepsilon, Y) \rightarrow (r, \varepsilon)[/math]
Данный автомат будет являться ДМП автоматом с допуском по пустому стеку в нормальной форме.
Автомат с единственным состоянием
| Определение: |
| Автомат с единственным состоянием (англ. Single State Push Down Automata, SDA) называется такой автомат [math]M[/math], представленный тройкой: входной алфавит на ленте [math]\Sigma[/math], стековым алфавит [math]\Gamma[/math] и множеством переходов [math]\Delta[/math].
Переходы в таком автомате имеют вид:
- [math](S, a) \rightarrow \alpha[/math], где [math]a \in \Sigma[/math], [math]S \in \Gamma[/math], [math]\alpha \in \Gamma^*[/math]
|
| Определение: |
| Множество слов выводимых из конфигурации [math]L(\alpha) = \{ \omega \in \Sigma^* : (\alpha, \omega) \rightarrow \varepsilon \}[/math]. |
| Определение: |
Автомат с единственным состоянием находится в нормальной форме, если все его переходы удовлетворяют условию:
- если [math](S, a) \rightarrow \alpha \in \Delta[/math], тогда [math]|\alpha| \leqslant 2[/math] и [math]L(\alpha) \neq \emptyset[/math].
|
Автомат с единственным состоянием можно сделать детерминированным, наложив следующее требование на переходы:
- если [math](S, a) \rightarrow \alpha \in \Delta[/math] и [math](S, a) \rightarrow \beta \in \Delta[/math], тогда [math]\alpha = \beta[/math].
Детерминированный автомат с единственным состоянием соответствует по мощности "простым грамматикам".
| Определение: |
Простая грамматика (англ. Simple Grammar) — такая грамматика, где все продукции имеют вид:
- [math]A \rightarrow \alpha B_1 B_2 \ldots B_n[/math],
где [math]\alpha[/math] — терминал, а все [math]B_i, i = 1 \ldots n[/math] — нетерминалы, и существует только одна продукция с парой [math]\langle A, \alpha \rangle[/math]. |
Однако, множество языков допускаемых детерминированным автоматом с единственным состоянием является строгим подмножеством языков ДМП автоматов, поэтому больший интерес представляют строгие автоматы с единственным состоянием.
Для этого вводится отношение эквивалентности [math]\equiv[/math] на множестве [math]\Gamma[/math], заданное разбиением [math]\Gamma[/math] на непересекающиеся подмножества.
Пример 1
- [math]\Sigma = \{a, b\}[/math]
- [math]\Gamma = \{A, C, X, Y\}[/math]
- [math]A, X[/math] — стартовые конфигурации
Переходы:
- [math](X, a) \rightarrow YX[/math]
- [math](X, b) \rightarrow \varepsilon[/math]
- [math](Y, b) \rightarrow X[/math]
- [math](A, a) \rightarrow C[/math]
- [math](A, b) \rightarrow \varepsilon[/math]
- [math](C, b) \rightarrow AA[/math]
Разбиение [math]\Gamma[/math] имеет вид [math]\{\{A\}, \{C\}, \{X\}, \{Y\}\}[/math].
Такой автомат будет детерминированным.
Пример 2
- [math]\Sigma = \{a, b, c\}[/math]
- [math]\Gamma = \{X, Y, Z\}[/math]
- [math]X, Z[/math] — стартовые конфигурации
Переходы:
- [math](X, a) \rightarrow X[/math]
- [math](X, b) \rightarrow \varepsilon[/math]
- [math](X, c) \rightarrow X[/math]
- [math](Y, a) \rightarrow \varepsilon[/math]
- [math](Y, c) \rightarrow YY[/math]
- [math](Z, b) \rightarrow \varepsilon[/math]
- [math](Z, c) \rightarrow Z[/math]
- [math](Z, c) \rightarrow YZ[/math]
Разбиение [math]\Gamma[/math] имеет вид [math]\{\{X\}, \{Y, Z\}\}[/math], что означает, что [math]Y \equiv Z[/math].
Отношение [math]\equiv[/math] можно расширить на последовательность стековых символов:
[math]\alpha \equiv \beta[/math] если:
- либо [math]\alpha = \beta[/math],
- либо [math]\alpha = \delta X \alpha'[/math], [math]\beta = \delta Y \beta'[/math], [math]X \equiv Y[/math] и [math]X \neq Y[/math].
Свойства [math]\equiv[/math]:
- [math]\alpha\beta \equiv \alpha \Leftrightarrow \beta = \varepsilon[/math].
- [math]\alpha \equiv \beta \Leftrightarrow \delta\alpha \equiv \delta\beta[/math].
- Если [math]\alpha \equiv \beta[/math] и [math]\gamma \equiv \delta[/math], тогда [math]\alpha\gamma \equiv \beta\delta[/math].
- Если [math]\alpha \equiv \beta[/math] и [math]\alpha \neq \beta[/math], тогда [math]\alpha\gamma \equiv \beta\delta[/math].
- Если [math]\alpha\gamma \equiv \beta\delta[/math] и [math]|\alpha| = |\beta|[/math], тогда [math]\alpha \equiv \beta[/math].
| Определение: |
Отношение [math]\equiv[/math] на множестве [math]\Gamma[/math] является строгим (англ. strict), если выполняются следующие условия:
- Если [math]X \equiv Y[/math], [math](X, a) \rightarrow \alpha[/math] и [math](Y, a) \rightarrow \beta[/math], тогда [math]\alpha \equiv \beta[/math].
- Если [math]X \equiv Y[/math], [math](X, a) \rightarrow \alpha[/math] и [math](Y, a) \rightarrow \alpha[/math], тогда [math]X = Y[/math].
|
| Определение: |
| Автомат с единственным состоянием с заданным разбиением [math]\Gamma[/math] является строгим (англ. strict), если отношение [math]\equiv[/math] строгое на множестве [math]\Gamma[/math]. |
Определение конфигураций автомата с единственным состоянием расширяется на наборы из последовательностей символов стека [math]\{ \alpha_1, \ldots , \alpha_n \}[/math], которые записываются в виде суммы [math]\alpha_1 + \ldots + \alpha_n[/math].
Две суммы конфигураций считаются эквивалентными (записывается через [math]=[/math]), если они представляют собой один и тот же набор.
Язык суммы конфигураций определяется — [math]L(\alpha_1 + \ldots + \alpha_n) = \bigcup\limits_{i = 1}^{n}L(\alpha_i)[/math]
| Определение: |
| Сумма конфигураций [math]\beta_1 + \ldots + \beta_n[/math] называется допустимой (англ. admissible), если [math]\beta_i \equiv \beta_j[/math] для всех элементов суммы, и [math]\beta_i \neq \beta_j[/math] при [math]i \neq j[/math]. |
Таким образом [math]\emptyset[/math] — тоже допустимо.
Некоторые суммы из второго примера: [math]XX[/math], [math]ZZZ + ZZY[/math], [math]YX + Z[/math], [math]Z + YZ[/math] и [math]Z + YZ + YYZ[/math] — все эти суммы допустимые, в то время как [math]X + Y[/math] будет недопустима, так как [math]X \not\equiv Y[/math].
Строгий автомат с единственным состоянием можно сделать детерминированным, заменив множество переходов [math]\Delta[/math] на [math]\Delta'[/math]:
для каждого символа [math]X \in \Gamma[/math] и [math]a \in \Sigma[/math] переходы вида
[math](X, a) \rightarrow \alpha_1, \ldots , (X, a) \rightarrow \alpha_n[/math] из [math]\Delta[/math]
заменяются на один переход [math](X, a) \rightarrow \alpha_1 + \ldots + \alpha_n[/math].
Таким образом для каждого [math]X \in \Gamma[/math] и [math]a \in \Sigma[/math] будет уникальный переход [math](X, a) \rightarrow \sum{\alpha_i}[/math] из [math]\Delta'[/math].
Связь ДМП автомата в нормальной форме и автомата с единственным состоянием
| Утверждение: |
|
| [math]\triangleright[/math] |
|
Пусть задан ДМП автомат в нормальной форме в виде четырех множеств [math]Q, \Sigma, \Gamma, \Delta[/math].
- Для двух состояний [math]p, q \in Q[/math] и [math]X \in \Gamma[/math] заведём новый символ стека [math][pXq][/math].
- Для переходов для данного [math]a \in \Sigma[/math]:
- если [math](p, a, X) \rightarrow (q, \varepsilon) \in \Delta[/math], тогда [math]([pXq], a) \rightarrow \varepsilon[/math];
- если [math](p, a, X) \rightarrow (q, Y) \in \Delta[/math], тогда [math]([pXr], a) \rightarrow [qYr][/math] для всех [math]r \in Q[/math];
- если [math](p, a, X) \rightarrow (q, YZ) \in \Delta[/math], тогда [math]([pXr], a) \rightarrow [qYp'][p'Zr][/math] для всех [math]r,p' \in Q[/math].
- [pSq] считается [math]\varepsilon[/math]-символом, если [math](p, \varepsilon, X) \rightarrow (q, \varepsilon) \in \Delta[/math]. Все [math]\varepsilon[/math]-символы удаляются из правой части переходов, полученных в предыдущем пункте.
Полученный автомат с единственным состоянием также находится в нормальной форме. Детерминируем новый автомат, чтобы сохранить детерминированность.
Таким образом каждая конфигурация вида [math]pX_1X_2 \ldots X_n[/math] из исходного автомата была трансформирована в [math]sum(p\alpha) = \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]}[/math] и [math]L(p\alpha) = L(sum(p\alpha))[/math]. |
| [math]\triangleleft[/math] |
Применим алгоритм к самому первому примеру и получим следующее:
- [math](X, a) \rightarrow X[/math]
- [math](Y, a) \rightarrow \varepsilon[/math]
- [math](Z, a) \rightarrow \emptyset[/math]
- [math](X, b) \rightarrow \varepsilon[/math]
- [math](Y, b) \rightarrow \emptyset[/math]
- [math](Z, b) \rightarrow \varepsilon[/math]
- [math](X, c) \rightarrow X[/math]
- [math](Y, c) \rightarrow YY[/math]
- [math](Z, c) \rightarrow YZ + Z[/math], где
- [math]X = [pXp][/math]
- [math]Y = [pYp][/math]
- [math]Z = [pYr][/math]
Применение
Нормализация ДМП автоматов используется в задаче проверки их на эквивалентность.
Для этого автоматы переводятся в нормальную форму, а затем в автоматы с единственным состоянием, для которых эта задача разрешима, следовательно разрешима и изначальная задача.
См. также
Источники информации
