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

Материал из Викиконспекты
Перейти к: навигация, поиск
(1)
 
(Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.)
Строка 25: Строка 25:
  
 
===Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.===
 
===Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.===
Создадим систему регулярных выражений с одним регулярным выражением, неизвестным для каждого состояния в ДКА, а затем решим систему для R_λ, где R_λ – регулярное выражение, связанное с начальным состоянием q_λ. Строим уравнения следующим образом: для каждого состояния q_i уравнение для R_i является объединением термов. Переход a из q_i в q_j обозначим за aR_i. Это приводит к системе уравнений вида:
+
Создадим систему регулярных выражений для каждого состояния в ДКА, а затем решим систему для регулярных выражений <tex>R_i</tex>, связанных с терминальным состояниями <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>
Строка 36: Строка 36:
 
</tex>
 
</tex>
  
где a_x = пустое мн если нет перехода от R_i к R_j.
+
где <tex>a_x</tex> = если нет перехода от <tex>R_i</tex> к <tex>R_j</tex>.
 +
Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:
  
Решение системы - регулярные выражения для терминальных состояний. Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:
+
Уравнение вида R = Q + RP, где P <tex>\ne \varepsilon</tex>, имеет решение R = QP*.
 
 
Уравнение вида R = Q + RP, где P != \varepsilon, имеет решение R = QP*.
 
  
 
Пример
 
Пример
  
 
Найти: Регулярное выражение, удовлетворяющее данному ДКА.
 
Найти: Регулярное выражение, удовлетворяющее данному ДКА.
 +
 
Решение:
 
Решение:
 +
 
<tex>
 
<tex>
 
\begin{cases}
 
\begin{cases}
Строка 51: Строка 52:
 
R_2 = a*R_1  \\
 
R_2 = a*R_1  \\
 
R_3 = b*R_1 \\
 
R_3 = b*R_1 \\
R_4 = a*R_2 + b*R_3 + a*R_4 + b*R_4  
+
R_4 = a*R_2 + b*R_3 + a*R_4 + b*R_4 + \varepsilon
 
\end{cases}
 
\end{cases}
 
</tex>
 
</tex>
 +
 
Рассмотрим первое терминальное состояние:
 
Рассмотрим первое терминальное состояние:
R_1 = \varepsilon + abR_1 + baR_1 = = \varepsilon + R_1(ab+ba)
+
 
 +
<tex>R_1 = \varepsilon + abR_1 + baR_1 = \varepsilon + R_1(ab+ba)</tex>
 +
 
 
Воспользуемся теоремой Ардена:  
 
Воспользуемся теоремой Ардена:  
R_1=(ab+ba)^*
+
 
 +
<tex>R_1=(ab+ba)^*</tex>
 +
 
 
Рассмотрим второе терминальное состояние :
 
Рассмотрим второе терминальное состояние :
R_4=R_1(aa+bb)+R_4(a+b)
+
 
R_4=R_1(aa+bb)(a+b)^*
+
<tex>R_4=R_1(aa+bb)+R_4(a+b)=R_1(aa+bb)(a+b)^*</tex>
Объединим выражения для терминальных состояний и получим искомое регулярное выражениею
+
 
R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)
+
Объединим выражения для терминальных состояний и получим искомое регулярное выражение:
 +
 
 +
<tex>R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)</tex>

Версия 16:53, 31 декабря 2020

п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) Преобразуем НКА в ДКА и минимизируем ДКА:


Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.

Создадим систему регулярных выражений для каждого состояния в ДКА, а затем решим систему для регулярных выражений [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*.

Пример

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

Решение:

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