Редактирование: Нормальная форма ДМП-автомата

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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| \leqslant 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, \varepsilon, S) \rightarrow (q, \alpha) \in \Delta</tex>, то <tex>\alpha = \varepsilon</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> нельзя ничего вывести).
 
}}
 
}}
Строка 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 = \varepsilon</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>
 
}}
 
}}
  
Строка 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, \varepsilon) \in \Delta</tex>, тогда <tex>([pXq], a) \rightarrow \varepsilon</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>\varepsilon</tex>-символом, если <tex>(p, \varepsilon, X) \rightarrow (q, \varepsilon) \in \Delta</tex>. Все <tex>\varepsilon</tex>-символы удаляются из правой части переходов, полученных в предыдущем пункте.
 
# [pSq] считается <tex>\varepsilon</tex>-символом, если <tex>(p, \varepsilon, X) \rightarrow (q, \varepsilon) \in \Delta</tex>. Все <tex>\varepsilon</tex>-символы удаляются из правой части переходов, полученных в предыдущем пункте.
 
Полученный автомат с единственным состоянием также находится в нормальной форме. Детерминируем новый автомат, чтобы сохранить детерминированность.
 
Полученный автомат с единственным состоянием также находится в нормальной форме. Детерминируем новый автомат, чтобы сохранить детерминированность.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)