Нормальная форма ДМП-автомата — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(New)
(Применение)
 
(не показаны 2 промежуточные версии 1 участника)
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|definition=ДМП в '''нормальной форме''' (англ. ''Normal Form'') называется такой [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|детерминированный автомат с магазинной памятью]] <tex>M</tex>, представленный конечным набором состояний <tex>Q</tex>, входным алфавитом на ленте <tex>\Sigma</tex>, стековым алфавитом <tex>\Gamma</tex> и множеством переходов <tex>\Delta</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 2</tex>, где <tex>\alpha \in \Gamma^*</tex> {{---}} последовательность стековых символов, <tex>S \in \Gamma</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, \epsilon, S) \rightarrow (q, \alpha) \in \Delta</tex>, то <tex>\alpha = \epsilon</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>\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, \epsilon) \}</tex>
+
|definition=Множество слов выводимых из конфигурации <tex>L(p, \sigma) = \{ \omega \in \Sigma^* : \exists q \in Q (p, \omega, \sigma) \rightarrow (q, \varepsilon) \}</tex>.
 
}}
 
}}
  
Строка 21: Строка 21:
 
и переходы имеют следующий вид:
 
и переходы имеют следующий вид:
 
: <tex>(p, a, X) \rightarrow (p, X)</tex>
 
: <tex>(p, a, X) \rightarrow (p, X)</tex>
: <tex>(p, b, X) \rightarrow (p, \epsilon)</tex>
+
: <tex>(p, b, X) \rightarrow (p, \varepsilon)</tex>
 
: <tex>(p, c, X) \rightarrow (p, X)</tex>
 
: <tex>(p, c, X) \rightarrow (p, X)</tex>
: <tex>(r, \epsilon, X) \rightarrow (p, \epsilon)</tex>
+
: <tex>(r, \varepsilon, X) \rightarrow (p, \varepsilon)</tex>
: <tex>(p, a, Y) \rightarrow (p, \epsilon)</tex>
+
: <tex>(p, a, Y) \rightarrow (p, \varepsilon)</tex>
: <tex>(p, b, Y) \rightarrow (r, \epsilon)</tex>
+
: <tex>(p, b, Y) \rightarrow (r, \varepsilon)</tex>
 
: <tex>(p, c, Y) \rightarrow (p, YY)</tex>
 
: <tex>(p, c, Y) \rightarrow (p, YY)</tex>
: <tex>(r, \epsilon, Y) \rightarrow (r, \epsilon)</tex>
+
: <tex>(r, \varepsilon, Y) \rightarrow (r, \varepsilon)</tex>
Данный автомат будет являтся [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|ДМП автоматом с допуском по пустому стеку]] в нормальной форме.
+
Данный автомат будет являться [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку|ДМП автоматом с допуском по пустому стеку]] в нормальной форме.
  
 
== Автомат с единственным состоянием ==
 
== Автомат с единственным состоянием ==
Строка 38: Строка 38:
  
 
{{Определение
 
{{Определение
|definition=Множество слов выводиых из конфигурации <tex>L(\alpha) = \{ \omega \in \Sigma^* : (\alpha, \omega) \rightarrow \epsilon \}</tex>
+
|definition=Множество слов выводимых из конфигурации <tex>L(\alpha) = \{ \omega \in \Sigma^* : (\alpha, \omega) \rightarrow \varepsilon \}</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=Автомат с единственным состоянием находится в '''нормальной форме''', если все его переходы удовлетворяют условию:
 
|definition=Автомат с единственным состоянием находится в '''нормальной форме''', если все его переходы удовлетворяют условию:
: если <tex>(S, a) \rightarrow \alpha \in \Delta</tex>, тогда <tex>|\alpha| \le 2</tex> и <tex>L(\alpha) \neq \emptyset</tex>
+
: если <tex>(S, a) \rightarrow \alpha \in \Delta</tex>, тогда <tex>|\alpha| \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>
+
: если <tex>(S, a) \rightarrow \alpha \in \Delta</tex> и <tex>(S, a) \rightarrow \beta \in \Delta</tex>, тогда <tex>\alpha = \beta</tex>.
 
Детерминированный автомат с единственным состоянием соответствует по мощности "простым грамматикам".
 
Детерминированный автомат с единственным состоянием соответствует по мощности "простым грамматикам".
  
 
{{Определение
 
{{Определение
 
|definition='''Простая грамматика''' (англ. ''Simple Grammar'') {{---}} такая грамматика, где все продукции имеют вид:
 
|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>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> на непересекающиеся подмоножества.
+
Для этого вводится отношение эквивалентности <tex>\equiv</tex> на множестве <tex>\Gamma</tex>, заданное разбиением <tex>\Gamma</tex> на непересекающиеся подмножества.
  
 
'''Пример 1'''
 
'''Пример 1'''
Детерминированный стековый автомат
 
 
: <tex>\Sigma = \{a, b\}</tex>
 
: <tex>\Sigma = \{a, b\}</tex>
 
: <tex>\Gamma = \{A, C, X, Y\}</tex>
 
: <tex>\Gamma = \{A, C, X, Y\}</tex>
Строка 66: Строка 66:
 
Переходы:
 
Переходы:
 
: <tex>(X, a) \rightarrow YX</tex>
 
: <tex>(X, a) \rightarrow YX</tex>
: <tex>(X, b) \rightarrow \epsilon</tex>
+
: <tex>(X, b) \rightarrow \varepsilon</tex>
 
: <tex>(Y, b) \rightarrow X</tex>
 
: <tex>(Y, b) \rightarrow X</tex>
 
: <tex>(A, a) \rightarrow C</tex>
 
: <tex>(A, a) \rightarrow C</tex>
: <tex>(A, b) \rightarrow \epsilon</tex>
+
: <tex>(A, b) \rightarrow \varepsilon</tex>
 
: <tex>(C, b) \rightarrow AA</tex>
 
: <tex>(C, b) \rightarrow AA</tex>
Разбиение <tex>\Gamma</tex> имеет вид <tex>\{\{A\}, \{C\}, \{X\}, \{Y\}\}</tex>
+
Разбиение <tex>\Gamma</tex> имеет вид <tex>\{\{A\}, \{C\}, \{X\}, \{Y\}\}</tex>.
 
Такой автомат будет детерминированным.
 
Такой автомат будет детерминированным.
  
Строка 80: Строка 80:
 
Переходы:
 
Переходы:
 
: <tex>(X, a) \rightarrow X</tex>
 
: <tex>(X, a) \rightarrow X</tex>
: <tex>(X, b) \rightarrow \epsilon</tex>
+
: <tex>(X, b) \rightarrow \varepsilon</tex>
 
: <tex>(X, c) \rightarrow X</tex>
 
: <tex>(X, c) \rightarrow X</tex>
: <tex>(Y, a) \rightarrow \epsilon</tex>
+
: <tex>(Y, a) \rightarrow \varepsilon</tex>
 
: <tex>(Y, c) \rightarrow YY</tex>
 
: <tex>(Y, c) \rightarrow YY</tex>
: <tex>(Z, b) \rightarrow \epsilon</tex>
+
: <tex>(Z, b) \rightarrow \varepsilon</tex>
 
: <tex>(Z, c) \rightarrow Z</tex>
 
: <tex>(Z, c) \rightarrow Z</tex>
 
: <tex>(Z, c) \rightarrow YZ</tex>
 
: <tex>(Z, c) \rightarrow YZ</tex>
Строка 92: Строка 92:
  
 
<tex>\alpha \equiv \beta</tex> если:
 
<tex>\alpha \equiv \beta</tex> если:
# либо <tex>\alpha = \beta</tex>
+
: либо <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>.
+
: либо <tex>\alpha = \delta X \alpha'</tex>, <tex>\beta = \delta Y \beta'</tex>, <tex>X \equiv Y</tex> и <tex>X \neq Y</tex>.
  
 
'''Свойства''' <tex>\equiv</tex>:
 
'''Свойства''' <tex>\equiv</tex>:
# <tex>\alpha\beta \equiv \alpha \Leftrightarrow \beta = \epsilon</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 \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>\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 \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>
+
# Если <tex>\alpha\gamma \equiv \beta\delta</tex> и <tex>|\alpha| = |\beta|</tex>, тогда <tex>\alpha \equiv \beta</tex>.
  
 
{{Определение
 
{{Определение
|definition=Отношение <tex>\equiv</tex> на множестве <tex>\Gamma</tex> является '''строгим''' (англ. ''strict'') {{---}}, если выполняются следующие условия:
+
|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 \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>
+
# Если <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> является '''строгим''', если отношение <tex>\equiv</tex> строгое на множестве <tex>\Gamma</tex>.
+
|definition=Автомат с единственным состоянием с заданным разбиением <tex>\Gamma</tex> является '''строгим''' (англ. ''strict''), если отношение <tex>\equiv</tex> строгое на множестве <tex>\Gamma</tex>.
 
}}
 
}}
  
  
Опеределение конфигураций автомата с единственным состоянием расшириряется на наборы из последовательностей символов стека <tex>\{ \alpha_1, \ldots , \alpha_n \}</tex>, которые записываются в виде суммы <tex>\alpha_1 + \ldots + \alpha_n</tex>.
+
Определение конфигураций автомата с единственным состоянием расширяется на наборы из последовательностей символов стека <tex>\{ \alpha_1, \ldots , \alpha_n \}</tex>, которые записываются в виде суммы <tex>\alpha_1 + \ldots + \alpha_n</tex>.
  
Две суммы конфигураций считаются эквивалентными (записывается через <tex>=</tex>), если они представляют из себя один и тот же набор.
+
Две суммы конфигураций считаются эквивалентными (записывается через <tex>=</tex>), если они представляют собой один и тот же набор.
  
Язык суммы конфигураций определяется {{---}} <tex>L(\alpha_1 + \ldots + \alpha_n) = \bigcup\{L(\alpha_i) : i = 1 \ldots n\}</tex>
+
Язык суммы конфигураций определяется {{---}} <tex>L(\alpha_1 + \ldots + \alpha_n) = \bigcup\limits_{i = 1}^{n}L(\alpha_i)</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>.
+
|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>\emptyset</tex> {{---}} тоже допустимо.
Строка 129: Строка 129:
 
<tex>(X, a) \rightarrow \alpha_1, \ldots , (X, a) \rightarrow \alpha_n</tex> из <tex>\Delta</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, 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>X \in \Gamma</tex> и <tex>a \in \Sigma</tex> будет уникальный переход <tex>(X, a) \rightarrow \sum{\alpha_i}</tex> из <tex>\Delta'</tex>.
  
 
== Связь ДМП автомата в нормальной форме и автомата с единственным состоянием ==
 
== Связь ДМП автомата в нормальной форме и автомата с единственным состоянием ==
Строка 136: Строка 136:
 
|proof=
 
|proof=
 
Пусть задан ДМП автомат в нормальной форме в виде четырех множеств <tex>Q, \Sigma, \Gamma, \Delta</tex>.
 
Пусть задан ДМП автомат в нормальной форме в виде четырех множеств <tex>Q, \Sigma, \Gamma, \Delta</tex>.
# Для двух состояний <tex>p, q \in Q</tex> и <tex>X \in \Gamma</tex> заведём новый символ стека <tex>[pXq]</tex>
+
# Для двух состояний <tex>p, q \in Q</tex> и <tex>X \in \Gamma</tex> заведём новый символ стека <tex>[pXq]</tex>.
# Для переходов сначала для данного <tex>a \in \Sigma</tex>:
+
# Для переходов для данного <tex>a \in \Sigma</tex>:
: если <tex>(p, a, X) \rightarrow (q, \epsilon) \in \Delta</tex>, тогда <tex>([pXq], a) \rightarrow \epsilon</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, 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>
+
#* если <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>\epsilon</tex>-символом, если <tex>(p, \epsilon, X) \rightarrow (q, \epsilon) \in \Delta</tex>. Все <tex>\epsilon</tex>-символы удаляются из правой части переходов, полученных в предыдущем пункте.
+
# [pSq] считается <tex>\varepsilon</tex>-символом, если <tex>(p, \varepsilon, X) \rightarrow (q, \varepsilon) \in \Delta</tex>. Все <tex>\varepsilon</tex>-символы удаляются из правой части переходов, полученных в предыдущем пункте.
 
Полученный автомат с единственным состоянием также находится в нормальной форме. Детерминируем новый автомат, чтобы сохранить детерминированность.
 
Полученный автомат с единственным состоянием также находится в нормальной форме. Детерминируем новый автомат, чтобы сохранить детерминированность.
Таким образом каждая конфигурация вида <tex>pX_1X_2 \ldots X_n</tex> из исходного автомата была трансформирована в <tex>sum(p\alpha) = \sum_{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>pX_1X_2 \ldots X_n</tex> из исходного автомата была трансформирована в <tex>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]}</tex> и <tex>L(p\alpha) = L(sum(p\alpha))</tex>.
 
}}
 
}}
  
 
Применим алгоритм к самому первому примеру и получим следующее:
 
Применим алгоритм к самому первому примеру и получим следующее:
 
: <tex>(X, a) \rightarrow X</tex>
 
: <tex>(X, a) \rightarrow X</tex>
: <tex>(Y, a) \rightarrow \epsilon</tex>
+
: <tex>(Y, a) \rightarrow \varepsilon</tex>
 
: <tex>(Z, a) \rightarrow \emptyset</tex>
 
: <tex>(Z, a) \rightarrow \emptyset</tex>
: <tex>(X, b) \rightarrow \epsilon</tex>
+
: <tex>(X, b) \rightarrow \varepsilon</tex>
 
: <tex>(Y, b) \rightarrow \emptyset</tex>
 
: <tex>(Y, b) \rightarrow \emptyset</tex>
: <tex>(Z, b) \rightarrow \epsilon</tex>
+
: <tex>(Z, b) \rightarrow \varepsilon</tex>
 
: <tex>(X, c) \rightarrow X</tex>
 
: <tex>(X, c) \rightarrow X</tex>
 
: <tex>(Y, c) \rightarrow YY</tex>
 
: <tex>(Y, c) \rightarrow YY</tex>
Строка 161: Строка 161:
 
: <tex>Z = [pYr]</tex>
 
: <tex>Z = [pYr]</tex>
  
== Примение ==
+
== Применение ==
Существует задача об определении эквивалентности двух [[Детерминированные автоматы с магазинной памятью|ДМП автоматов]] (два ДМП автомата <tex>M_1</tex> и <tex>М_2</tex> эквивалетны, если <tex>L(M_1) = L(M_2)</tex>).
+
Нормализация [[Детерминированные автоматы с магазинной памятью|ДМП автоматов]] используется в задаче проверки их на [[Эквивалентность ДМП автоматов|эквивалентность]].
Для этого автоматы переводятся в нормальную форму, а потом переводятся в автоматы с единственным состоянием, для которых эта задача разрешима.
+
Для этого автоматы переводятся в нормальную форму, а затем в автоматы с единственным состоянием, для которых эта задача разрешима, следовательно разрешима и изначальная задача.
  
 
== См. также ==
 
== См. также ==

Текущая версия на 00:06, 17 января 2017

Определение[править]

Определение:
ДМП в нормальной форме (англ. Normal Form) называется такой детерминированный автомат с магазинной памятью [math]M[/math], представленный конечным набором состояний [math]Q[/math], входным алфавитом на ленте [math]\Sigma[/math], стековым алфавитом [math]\Gamma[/math] и множеством переходов [math]\Delta[/math], который удовлетворяет следующим условиям:
  1. Если [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].
  2. Если [math](p, \varepsilon, S) \rightarrow (q, \alpha) \in \Delta[/math], то [math]\alpha = \varepsilon[/math].
  3. [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]:

  1. [math]\alpha\beta \equiv \alpha \Leftrightarrow \beta = \varepsilon[/math].
  2. [math]\alpha \equiv \beta \Leftrightarrow \delta\alpha \equiv \delta\beta[/math].
  3. Если [math]\alpha \equiv \beta[/math] и [math]\gamma \equiv \delta[/math], тогда [math]\alpha\gamma \equiv \beta\delta[/math].
  4. Если [math]\alpha \equiv \beta[/math] и [math]\alpha \neq \beta[/math], тогда [math]\alpha\gamma \equiv \beta\delta[/math].
  5. Если [math]\alpha\gamma \equiv \beta\delta[/math] и [math]|\alpha| = |\beta|[/math], тогда [math]\alpha \equiv \beta[/math].


Определение:
Отношение [math]\equiv[/math] на множестве [math]\Gamma[/math] является строгим (англ. strict), если выполняются следующие условия:
  1. Если [math]X \equiv Y[/math], [math](X, a) \rightarrow \alpha[/math] и [math](Y, a) \rightarrow \beta[/math], тогда [math]\alpha \equiv \beta[/math].
  2. Если [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].

  1. Для двух состояний [math]p, q \in Q[/math] и [math]X \in \Gamma[/math] заведём новый символ стека [math][pXq][/math].
  2. Для переходов для данного [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].
  3. [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]

Применение[править]

Нормализация ДМП автоматов используется в задаче проверки их на эквивалентность. Для этого автоматы переводятся в нормальную форму, а затем в автоматы с единственным состоянием, для которых эта задача разрешима, следовательно разрешима и изначальная задача.

См. также[править]

Источники информации[править]