317
правок
Изменения
→Обычный вариант
Рассмотрим автоматный язык <tex>L</tex> и ДКА для него. Для доказательства теоремы достаточно построить регулярное выражение, порождающее язык <tex>L</tex>.
Пусть наш автомат состоит из <tex>n</tex> состояний, и состояние <tex>0</tex> {{---}} — стартовое. Также пусть <tex>L_i</tex> {{---}} — язык, состоящий из слов, которые приводят из состояния <tex>i</tex> в терминальное.
Заметим, что <tex>L_i = \sum bigcup c L_j</tex> для всех <tex> c \in \Sigma </tex> и <tex>j</tex> таких, что <tex>\delta(i, c)=j</tex>. Действительно, если по слову <tex> \alpha </tex> из состояния <tex>j</tex> мы можем попасть в терминальное состояние, а между состояниями <tex> i </tex> и <tex> j </tex> есть переход по символу <tex> c </tex>, то слово <tex> c \alpha </tex> принаджелит принадлежит языку <tex>L_i</tex>. Также, если <tex>\epsilon varepsilon \in L_0L_i</tex>, то есть, если стартовое состояние является и терминальным тоже, то добавим в сумму для <tex>L_0\varepsilon</tex> и в объединение для <tex>\epsilonL_i</tex>.
Мы получили [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | систему]] из <tex>n</tex> регулярных выражений с <tex>n</tex> неизвестными, причем для всех <tex> \varepsilon \notin \alpha_{ij}</tex> (<tex> \alpha_{ij} </tex> {{---}} коэффициент перед <tex> j </tex>-й переменной в <tex> i </tex> и -м [[Решение уравнений в регулярных выражениях#Решение системы уравнений в регулярных выражениях | уравнении]]) для всех <tex> j i </tex> и <tex> \epsilon \notin \alpha_{ij}j </tex>, так как в автомате нет <tex> \epsilon varepsilon </tex>-переходов, а следовательно, система имеет единственное решение. Также заметим, что <tex>L_0</tex> содержит все слова, по которым из стартового состояния можно дойти до терминального, но тогда <tex>L_0 = L</tex>.
В итоге мы построили систему уравнений в регулярных выражениях, решив которую, мы получим реглярное регулярное выражение , порождающее язык <tex>L</tex>.
}}
Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по [[Теорема Клини (совпадение классов автоматных и регулярных языков) | теореме Клини]]. Кроме того, построение регулярного выражения таким образом обычно гораздо проще (выполняется за меньшее количество шагов).
== Пример ==
=== Система уравнений ===[[fileФайл:Автомат2at_least_one_zero.png|450px|right]]Найдем регулярное выражение для языка двоичных представлений чисел кратных трем, в которых есть хотя бы один ноль. Для этого составим уравнение, добавляя соответствующие переменные в правую часть при наличии перехода по символу, а так же <tex>\varepsilon</tex> для терминального состояния, как это указано в доказательстве.
<tex>
\begin{cases}
\end{cases}
</tex>
Найдем <tex> L_1 </tex>: <tex>L_1 = 1L_1</tex>. Так как <tex> \varepsilon \notin 1 </tex>, то <tex>L_1 = 1^*</tex>. Выразим <tex>L_2</tex>через <tex> L_1 </tex>: <tex>L_2 = 0L_1 + 0L_2 + 1L_2 + \varepsilon</tex> Откуда <tex>L_2 = 01^* (0 + 1)^*</tex>. === Обычный вариант === Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант).Для начала построим таблицу, согласно [[Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков) | теореме]] по шагам: {| border="1" class="wikitable" style="width: 250px; height: 250px; float: left;"!style="background:#41aef0"|Выражение!style="background:#41aef0"|Значения|-|<tex>R_{11}^{(0)}</tex>|<tex>\varepsilon + 1</tex>|-|<tex>R_{12}^{(0)}</tex>|<tex>0</tex>|-|<tex>R_{21}^{(0)}</tex>|<tex>\varnothing</tex>|-|<tex>R_{22}^{(0)}</tex>|<tex>(\varepsilon + 0 + 1)</tex>|}<div style="clear:both;"></div> Например, в выражении <tex>R_{11}^{(0)}</tex> присутствует член <tex>\varepsilon</tex>, потому что и начальным, и конечным является состояние <tex>1</tex>. Это выражение включает также <tex>1</tex>, поскольку существует путьиз состояния <tex>1</tex> в состояние <tex>1</tex> по входу <tex>1</tex>. Выражение <tex>R_{12}^{(0)}</tex> равно <tex>0</tex>, потому что есть дуга сметкой <tex>0</tex>, ведущая из состояния <tex>1</tex> в состояние <tex>2</tex>. Здесь нет члена <tex>\varepsilon</tex>, поскольку начальноеи конечное состояния различаются. И, наконец, <tex>R_{21}^{(0)} = \varnothing</tex>, так как нет путей, ведущих изсостояния <tex>2</tex> в состояние <tex>1</tex>.Теперь применим индукцию для построения более сложных выражений. Правило для вычисления выражения <tex>R_{ij}^{(1)}</tex> представляет собой пример общего правила из части теоремы Клини: <tex>R_{ij}^{(1)} = R_{ij}^{(0)} + R_{i1}^{(0)} (R_{11}^{(0)})^* R_{1j}^{(0)}</tex> {| border="1" class="wikitable" style="width:300px; height: 250px; float: left;"!style="background:#41aef0"|Выражение!style="background:#41aef0"|Прямая подстановка!style="background:#41aef0"|Упрощенное выражение|-|<tex>R_{11}^{(1)}</tex>|<tex>\varepsilon + 1 + (\varepsilon + 1)(\varepsilon + 1)^*(\varepsilon + 1)</tex>|<tex>1^*</tex>|-|<tex>R_{12}^{(1)}</tex>|<tex>0 + (\varepsilon + 1)(\varepsilon + 1)^*0</tex>|<tex>1^*0</tex>|-|<tex>R_{21}^{(1)}</tex>|<tex>\varnothing + \varnothing(\varepsilon + 1)^*(\varepsilon + 1)</tex>|<tex>\varnothing</tex>|-|<tex>R_{22}^{(1)}</tex>|<tex>\varepsilon + 0 + 1 + \varnothing(\varepsilon + 1)^*0</tex>|<tex>(\varepsilon + 0 + 1)</tex>|}<div style="clear:both;"></div> И, наконец, последний шаг индукции {| border="1" class="wikitable" style="width: 300px; height: 250px; float: left;"!style="background:#41aef0"|Выражение !style="background:#41aef0"|Упрощенное выражение (после подстановки)|-|<tex>R_{11}^{(1)}</tex>|<tex>1^*</tex>|-|<tex>R_{12}^{(1)}</tex>|<tex>1^*0(0 + 1)^*</tex>|-|<tex>R_{21}^{(1)}</tex>|<tex>\varnothing</tex>|-|<tex>R_{22}^{(1)}</tex>|<tex>(0 + 1)^*</tex>|}<div style="clear:both;"></div>
Окончательное регулярное выражение, эквивалентное автомату, строится путем объединения всех тех выражений, для которых первое состояниеявляется начальным, а второе {{---}} заключительным. В нашем примере <tex>1</tex>L_2 = {{---}} начальное состояние, а <tex>2</tex> {{---}} заключительное, поэтому нам нужно лишь выражение <tex>R_{12}^{(1)}</tex>, равное <tex>1^*0(00 0 + 1)L_2+01L_1^*</tex>.
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]