Изменения
→Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.
===Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.===
Создадим систему регулярных выражений с одним регулярным выражением, неизвестным для каждого состояния в ДКА, а затем решим систему для R_λрегулярных выражений <tex>R_i</tex>, где R_λ – регулярное выражение, связанное связанных с начальным состоянием q_λтерминальным состояниями <tex>q_i</tex>. Строим уравнения следующим образом: для каждого состояния <tex>q_i </tex> уравнение для <tex>R_i </tex> является объединением термовпереходов, ведущих в это состояние. Переход a из <tex>q_i </tex> в <tex>q_j </tex> обозначим за <tex>aR_i</tex>. Если <tex>q_i</tex> - терминальное состояние, то добавим в <tex>R_i</tex> <tex>\ne \varepsilon</tex>. Это приводит к системе уравнений вида:
<tex>
</tex>
где <tex>a_x </tex> = пустое мн ∅ если нет перехода от <tex>R_i </tex> к <tex>R_j</tex>.Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:
Пример
Найти: Регулярное выражение, удовлетворяющее данному ДКА.
Решение:
<tex>
\begin{cases}
R_2 = a*R_1 \\
R_3 = b*R_1 \\
R_4 = a*R_2 + b*R_3 + a*R_4 + b*R_4 + \varepsilon
\end{cases}
</tex>
Рассмотрим первое терминальное состояние:
<tex>R_1 = \varepsilon + abR_1 + baR_1 = = \varepsilon + R_1(ab+ba)</tex>
Воспользуемся теоремой Ардена:
<tex>R_1=(ab+ba)^*</tex>
Рассмотрим второе терминальное состояние :
<tex>R_4=R_1(aa+bb)+R_4(a+b)R_4=R_1(aa+bb)(a+b)^*</tex> Объединим выражения для терминальных состояний и получим искомое регулярное выражениеювыражение: <tex>R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)</tex>
