Участница:Наталья Юльцова — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Преобразование регулярного выражения в ДКА)
(Пример)
Строка 30: Строка 30:
 
| style="background-color:white;" | [[Файл:0+1.png|250px|thumb]]
 
| style="background-color:white;" | [[Файл:0+1.png|250px|thumb]]
 
|-align="center"
 
|-align="center"
|Далее считаем, что <tex>(0|1)</tex> это подвыражение вида R, и строим выражение <tex>(0|1)^*</tex>.
+
|Далее считаем, что <tex>(0|1)</tex> это подвыражение вида <tex>R</tex>, и строим выражение <tex>(0|1)^*</tex>.
 
| style="background-color:white;" | [[Файл:(0+1)star.png|250px|thumb]]
 
| style="background-color:white;" | [[Файл:(0+1)star.png|250px|thumb]]
 
|-align="center"
 
|-align="center"
|Выражение <tex>(0|1)^*1</tex> имеет вид RS, <tex>(0|1)^*1(0|1)</tex> имеет тот же вид.
+
|Выражение <tex>(0|1)^*1</tex> имеет вид <tex>RS</tex>, <tex>(0|1)^*1(0|1)</tex> имеет тот же вид.
 
| style="background-color:white;" | [[Файл:(0+1)star1(0+1).png|250px|thumb]]
 
| style="background-color:white;" | [[Файл:(0+1)star1(0+1).png|250px|thumb]]
 
|-align="center"
 
|-align="center"

Версия 22:51, 1 января 2021

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

Алгоритм

рис. 1 "Виды выражений"
  1. Преобразуем регулярное выражение в [math]\varepsilon[/math]-НКА.
  2. Устраним [math]\varepsilon[/math]-переходы.
  3. Построим по НКА эквивалентное ДКА по алгоритму Томпсона.

Преобразование регулярного выражения в [math]\varepsilon[/math]-НКА.

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

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

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

Пример

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

Регулярное выражение Автомат
Преобразуем регулярное выражение [math](0|1)^*1(0|1)[/math] в [math]\varepsilon[/math]-НКА. Построим сначала автомат для [math]0|1[/math]. Это выражение имеет вид [math]R|S[/math].
0+1.png
Далее считаем, что [math](0|1)[/math] это подвыражение вида [math]R[/math], и строим выражение [math](0|1)^*[/math].
(0+1)star.png
Выражение [math](0|1)^*1[/math] имеет вид [math]RS[/math], [math](0|1)^*1(0|1)[/math] имеет тот же вид.
(0+1)star1(0+1).png
Удалим [math]\varepsilon[/math]-переходы, согласно алгоритму из статьи, получим НКА.
RemoveEps.png
Преобразуем НКА в ДКА по алгоритму Томпсона и минимизируем ДКА
MinDKA.png

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

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

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

[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]

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

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

Пример

AutToReg.png

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

Решение:

[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 + \varepsilon \end{cases} [/math]

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

[math]R_1 = \varepsilon + abR_1 + baR_1 = \varepsilon + R_1(ab+ba)[/math]

Воспользуемся теоремой Ардена:

[math]R_1=(ab+ba)^*[/math]

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

[math]R_4=R_1(aa+bb)+R_4(a+b)=R_1(aa+bb)(a+b)^*[/math]

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

[math]R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)[/math]