403
правки
Изменения
→Пример
== Пример ==
Найдем регулярное выражение для языка двоичных представлений чисел кратных трем.
<tex>
\begin{cases}
L_0 = 0L_0+1L_1+\epsilon \\
L_1 = 1L_0+0L_2 \\
L_2 = 0L_1+1L_2
\end{cases}
</tex>
Выразим <tex>L_2</tex>:
<tex>L_2 = (00 + 1)L_2+01L_1</tex>.
Так как <tex> \epsilon \notin (00 + 1) </tex>, то <tex>L_2 = (00+1)^*01L_0</tex>.
Подставим <tex>L_2</tex> во второе уравнение, а потом получившееся выражение подставим в первое, чтобы найти <tex>L_0</tex>:
<tex>L_0 = 0L_0 + 11L_0 + 10(00+1)^*01L_0 + \epsilon </tex>.
Решив уравнение, получим что <tex>(0 + 11 + 10(00+1)^*01)^*</tex> {{---}} регулярное выражение, порождающее искомый язык. Отметим, что длина итогового регулярного выражения заметно короче, чем если бы мы строили его классическим способом.
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
