317
правок
Изменения
→Обычный вариант
}}
Отметим, что длина построенного таким образом регулярного выражения обычно заметно короче, чем если бы мы строили его по [[Теорема Клини (совпадение классов автоматных и регулярных языков) | теореме Клини]]. Кроме того, построение регулярного выражения таким образом обычно гораздо проще (выполняется за меньшее количество шагов).
== Пример ==
=== Система уравнений ===
[[Файл:at_least_one_zero.png|right]]
Найдем регулярное выражение для языка двоичных представлений чисел, в которых есть хотя бы один ноль. Для этого составим уравнение, добавляя соответствующие переменные в правую часть при наличии перехода по символу, а так же <tex>\varepsilon</tex> для терминального состояния, как это указано в доказательстве.
<tex>
Откуда <tex>L_2 = 01^* (0 + 1)^*</tex>.
=== Обычный вариант ===
Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант).
Для начала построим таблицу, согласно [[Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков) | теореме]] по шагам:
{| border="1" class="wikitable" style="width: 500px250px; height: 100px250px; 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> {{---}} начальное состояние, а <tex>2</tex> {{---}} заключительное, поэтому нам нужно лишь выражение <tex>R_{12}^{(1)}</tex>, равное <tex>1^*0(0 + 1)^*</tex>
Отметим, что первый вариант значительно короче. Для решения системы уравнений необходимо выполнить <tex>O(n)</tex> итераций, где <tex>n</tex> {{---}} число вершин. В каждом уравнении в худшем случае может быть <tex>|\Gamma| \cdot (n - 1)</tex> переменных в правой части {{---}} все возможные переходы по всем возможным состояниям. Теперь, для решения вторым вариантом, нам во-первых надо построить массив размера <tex>|\Gamma| \cdot n</tex> для всех переходов из всех состояний и выполнить столько же итераций, поскольку самый длинный путь в худшем случае будет проходить по всем переходам из всех вершин с возвращением в исходную, которая и будет являться терминальной, то есть в итоге сложность <tex>O((|\Gamma| \cdot n)^2)</tex>. Кроме того, в алгоритме на каждом шаге мы упрощали выражение, чтобы оно было более коротким. В общем случае длина выражения перед упрощением трудно поддается оценке, однако не стоит забывать про этот факт. В случае, если выражение не будет упрощаться, то по приведенной выше формуле итерации, оно, очевидно, с каждой итерацией будет значительно (степенная зависимость) расти.
== См. также ==
