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

Преобразование регулярного выражения в ДКА

Алгоритм

1. Преобразуем регулярное выражение в ε-НКА.
2. Устраним ε-переходы.
3. Построим по НКА эквивалентное ДКА по алгоритму Томпсона.

Преобразование регулярного выражения в ε-НКА.

Рассмотрим подробнее как преобразуется регулярное выражение в ε-НКА. Автомат для выражения строится композицией из автоматов, соответствующих подвыражениям.

Виды выражений:

1. Данное выражение имеет вид R|S для некоторых подвыражений R и S. Тогда ему соответствует автомат, представленный на рис. a.
2. Выражение имеет вид RS. Автомат для этой конкатенации представлен на рис. b.
3. Выражение имеет вид R* для некоторого подвыражения R. Используем автомат, представленный на рис. c.

Пример

Преобразовать регулярное выражение (0|1)*1(0|1) в ДКА.

1. Преобразуем регулярное выражение (0|1)*1(0|1) в ε-НКА. Построим сначала автомат для 0|1. Это выражение имеет вид R|S. Далее считаем, что (0|1) это подвыражение вида R, и строим выражение (0|1)*. Выражение (0|1)*1 имеет вид RS, (0|1)*1(0|1) имеет тот же вид.
2. Удалим ε-переходы, согласно алгоритму из статьи, получим НКА:
3. Преобразуем НКА в ДКА по алгоритму Томпсона и минимизируем ДКА.

Преобразование ДКА в регулярное выражение

Алгебраический метод Бжозовского

Создадим систему регулярных выражений для каждого состояния в ДКА, а затем решим систему для регулярных выражений $R_i$, связанных с терминальным состояниями $q_i$. Строим уравнения следующим образом: для каждого состояния $q_i$ уравнение $R_i$ является объединением переходов, ведущих в это состояние. Переход a из $q_i$ в $q_j$ обозначим за $aR_i$. Если $q_i$ - терминальное состояние, то добавим в $R_i$ $\ne \varepsilon$. Это приводит к системе уравнений вида:

$\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}$

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

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

Пример

Найти: Регулярное выражение, удовлетворяющее данному ДКА.

Решение:

$\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 + \varepsilon \end{cases}$

Рассмотрим первое терминальное состояние:

$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_1(aa+bb)(a+b)^*$

Объединим выражения для терминальных состояний и получим искомое регулярное выражение:

$R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)$