403
правки
Изменения
м
→Пример
<tex>
\begin{cases}
L_0 = 0L_0+1L_1+\epsilon varepsilon \\
L_1 = 1L_0+0L_2 \\
L_2 = 0L_1+1L_2
<tex>L_2 = (00 + 1)L_2+01L_1</tex>.
Так как <tex> \epsilon varepsilon \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 varepsilon </tex>.
Решив уравнение, получим что <tex>(0 + 11 + 10(00+1)^*01)^*</tex> {{---}} регулярное выражение, порождающее искомый язык. Отметим, что длина итогового регулярного выражения заметно короче, чем если бы мы строили его классическим способом.
== См. также ==
