Участница:Наталья Юльцова

п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. Это приводит к системе уравнений вида:

[math] \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} [/math]

где a_x = пустое мн если нет перехода от R_i к R_j.

Решение системы - регулярные выражения для терминальных состояний. Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:

Уравнение вида R = Q + RP, где P != \varepsilon, имеет решение R = QP*.

Пример

Найти: Регулярное выражение, удовлетворяющее данному ДКА. Решение: [math] \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} [/math] Рассмотрим первое терминальное состояние: 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)^*)