== Пример ==
[[fileФайл:Автомат2at_least_one_zero.png|450px|right]]Найдем регулярное выражение для языка двоичных представлений чисел кратных трем., в которых есть хотя бы один ноль
<tex>
\begin{cases}
L_0 L_1 = 0L_0+1L_1+\varepsilon \\L_1 L_2 = 1L_00L_1 +0L_2 \\L_2 = 0L_1+1L_2+ \varepsilon
\end{cases}
</tex>
Выразим <tex>L_2</tex> из третьего уравнения, подставив Найдем <tex> L_1 </tex> из второго:
<tex>L_2 L_1 = (00 + 1)L_2+01L_01L_1</tex>.
Так как <tex> \varepsilon \notin (00 + 1) </tex>, то <tex>L_2 L_1 = (00+1)^*01L_0</tex>.
Подставим Выразим <tex>L_2</tex> во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти через <tex>L_0L_1 </tex>:
<tex>L_0 L_2 = 0L_0 0L_1 + 11L_0 0L_2 + 10(00+1)^*01L_0 1L_2 + \varepsilon </tex>.
Решив уравнение, получим что Откуда <tex>(0 + 11 + 10L_2 = 01^* (00+1)^*01)^*</tex> . Теперь найдем регулярное выражение для этого же автомата с помощью теоремы Клини (обычный вариант).Для начала построим таблицу, согласно [[Теорема_Клини_(совпадение_классов_автоматных_и_регулярных_языков) | теореме]] по шагам: {{--| border="1" class="wikitable" style="width: 500px; height: 100px; float: left;"!style="background:#41aef0"|Выражение!style="background:#41aef0"|Значения|-|| |}} регулярное выражение, порождающее искомый язык.<div style="clear:both;"></div>
== См. также ==
