78
правок
Изменения
1
===пGреобразование регулярного выражения в ДКА.===
Задача: преобразовать регулярное выражение в ДКА.
Алгоритм:
1) Преобразовать регулярное выражение в ε-НКА. Будем пользоваться следующим правилом:
1. Для регулярного выражения A|B можем построить следующий КА:
2. Для регулярного выражения AB можем построить следующий КА:
3. Для регулярного выражения A* можем построить следующий КА:
2) Преобразовать ε-НКА в НКА (статья : Автоматы с eps-переходами. Eps-замыкание)
3) Преобразовать НКА в ДКА (статья : Построение по НКА эквивалентного ДКА, алгоритм Томпсона)
Пример: преобразовать регулярное выражение (0|1)*1(0|1) в ДКА.
1) Преобразуем регулярное выражение (0|1)*1(0|1) в ε-НКА.
Построим сначала автомат для 0|1. Для этого воспользуемся правилом 1.
Далее принимаем (0|1) за А и строим по правилу 3 выражение (0|1)*.
После по правилу 2 соединим (0|1)*, 1, и (0|1).
2) Удалим ε-переходы, получим НКА:
3) Преобразуем НКА в ДКА и минимизируем ДКА:
===Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.===
Создадим систему регулярных выражений с одним регулярным выражением, неизвестным для каждого состояния в ДКА, а затем решим систему для R_λ, где R_λ – регулярное выражение, связанное с начальным состоянием q_λ. Строим уравнения следующим образом: для каждого состояния q_i уравнение для R_i является объединением термов. Переход a из q_i в q_j обозначим за aR_i. Это приводит к системе уравнений вида:
<tex>
\begin{cases}
R_1 = a_1*R_1 + a_2*R_2 + a_3*R_3 + ... \\
R_2 = a_1*R_1 + a_2*R_2 + a_3*R_3 + ... + \varepsilon \\
... \\
R_m = a_1*R_1 + a_2*R_2 + a_3*R_3 + ... + \varepsilon
\end{cases}
</tex>
где a_x = пустое мн если нет перехода от R_i к R_j.
Решение системы - регулярные выражения для терминальных состояний. Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:
Уравнение вида R = Q + RP, где P != \varepsilon, имеет решение R = QP*.
Пример
Найти: Регулярное выражение, удовлетворяющее данному ДКА.
Решение:
<tex>
\begin{cases}
R_1 = b*R_2 + a*R_3 + \varepsilon \\
R_2 = a*R_1 \\
R_3 = b*R_1 \\
R_4 = a*R_2 + b*R_3 + a*R_4 + b*R_4
\end{cases}
</tex>
Рассмотрим первое терминальное состояние:
R_1 = \varepsilon + abR_1 + baR_1 = = \varepsilon + R_1(ab+ba)
Воспользуемся теоремой Ардена:
R_1=(ab+ba)^*
Рассмотрим второе терминальное состояние :
R_4=R_1(aa+bb)+R_4(a+b)
R_4=R_1(aa+bb)(a+b)^*
Объединим выражения для терминальных состояний и получим искомое регулярное выражениею
R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)
Задача: преобразовать регулярное выражение в ДКА.
Алгоритм:
1) Преобразовать регулярное выражение в ε-НКА. Будем пользоваться следующим правилом:
1. Для регулярного выражения A|B можем построить следующий КА:
2. Для регулярного выражения AB можем построить следующий КА:
3. Для регулярного выражения A* можем построить следующий КА:
2) Преобразовать ε-НКА в НКА (статья : Автоматы с eps-переходами. Eps-замыкание)
3) Преобразовать НКА в ДКА (статья : Построение по НКА эквивалентного ДКА, алгоритм Томпсона)
Пример: преобразовать регулярное выражение (0|1)*1(0|1) в ДКА.
1) Преобразуем регулярное выражение (0|1)*1(0|1) в ε-НКА.
Построим сначала автомат для 0|1. Для этого воспользуемся правилом 1.
Далее принимаем (0|1) за А и строим по правилу 3 выражение (0|1)*.
После по правилу 2 соединим (0|1)*, 1, и (0|1).
2) Удалим ε-переходы, получим НКА:
3) Преобразуем НКА в ДКА и минимизируем ДКА:
===Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.===
Создадим систему регулярных выражений с одним регулярным выражением, неизвестным для каждого состояния в ДКА, а затем решим систему для R_λ, где R_λ – регулярное выражение, связанное с начальным состоянием q_λ. Строим уравнения следующим образом: для каждого состояния q_i уравнение для R_i является объединением термов. Переход a из q_i в q_j обозначим за aR_i. Это приводит к системе уравнений вида:
<tex>
\begin{cases}
R_1 = a_1*R_1 + a_2*R_2 + a_3*R_3 + ... \\
R_2 = a_1*R_1 + a_2*R_2 + a_3*R_3 + ... + \varepsilon \\
... \\
R_m = a_1*R_1 + a_2*R_2 + a_3*R_3 + ... + \varepsilon
\end{cases}
</tex>
где a_x = пустое мн если нет перехода от R_i к R_j.
Решение системы - регулярные выражения для терминальных состояний. Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:
Уравнение вида R = Q + RP, где P != \varepsilon, имеет решение R = QP*.
Пример
Найти: Регулярное выражение, удовлетворяющее данному ДКА.
Решение:
<tex>
\begin{cases}
R_1 = b*R_2 + a*R_3 + \varepsilon \\
R_2 = a*R_1 \\
R_3 = b*R_1 \\
R_4 = a*R_2 + b*R_3 + a*R_4 + b*R_4
\end{cases}
</tex>
Рассмотрим первое терминальное состояние:
R_1 = \varepsilon + abR_1 + baR_1 = = \varepsilon + R_1(ab+ba)
Воспользуемся теоремой Ардена:
R_1=(ab+ba)^*
Рассмотрим второе терминальное состояние :
R_4=R_1(aa+bb)+R_4(a+b)
R_4=R_1(aa+bb)(a+b)^*
Объединим выражения для терминальных состояний и получим искомое регулярное выражениею
R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)
