317
правок
Изменения
→Пример
Для начала построим таблицу, согласно [[Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков) | теореме]] по шагам:
{| 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>
== См. также ==
