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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Преобразование регулярного выражения в ДКА)
(Источники информации)
 
(не показаны 62 промежуточные версии 3 участников)
Строка 1: Строка 1:
=Преобразование регулярного выражения в ДКА=  
+
==Преобразование регулярного выражения в ДКА==
  
==Алгоритм==
+
Чтобы преобразовать [[Регулярные языки: два определения и их эквивалентность| регулярное выражение]] в [[Детерминированные конечные автоматы|ДКА]], нужно:
  
# Преобразуем регулярное выражение в ε-НКА.
+
# Преобразовать регулярное выражение в [[Недетерминированные конечные автоматы|НКА]] с <tex>\varepsilon</tex>-переходами.
# [[Автоматы с eps-переходами. Eps-замыкание | Устраним ε-переходы.]]
+
# Устранить [[Автоматы с eps-переходами. Eps-замыкание | <tex>\varepsilon</tex>-переходы.]]
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | Построим по НКА эквивалентное ДКА по алгоритму Томпсона.]]
+
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | Построить]] по НКА эквивалентный ДКА.
  
===Преобразование регулярного выражения в ε-НКА.===
+
===Преобразование регулярного выражения в НКА===
  
Рассмотрим подробнее как преобразуется регулярное выражение в ε-НКА. Автомат для выражения строится композицией из автоматов, соответствующих
+
Преобразование проводится структурной индукцией по выражению <tex>R</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]]. Необходимо рекурсивно "спуститься" вглубь языка <tex>L(R)</tex>, дойдя до нулевого уровня - <tex>R_0</tex>. Автоматы, распознающие <tex>L(R_0)</tex> представлены на рис. 1, это базис.
подвыражениям.  
+
{| cellpadding="3"
 +
|[[Файл:базис.png|150px|thumb|center|рис. 1. a. <tex>\varepsilon</tex> б. <tex>\varnothing</tex> в. <tex>a</tex>]]
 +
|}
 +
Далее строится выражение <tex>\mathrm{R_{i+1}}</tex>, пока <tex>\mathrm{R_{i}} \ne R</tex> следующим образом:
  
Виды выражений:
+
# Выражение имеет вид <tex>R_i|S</tex>, для некоторых выражений <tex>R_i</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 2.a. Предполагаем, что <tex>R_i</tex> уже построено, а <tex>S</tex> строится по тому же алгоритму, что и <tex>R</tex>, значит, возможно построить <tex>\mathrm{R_{i+1}} = R_i|S</tex>
 +
# Выражение имеет вид <tex>R_iS</tex>. Автомат для этой конкатенации представлен на рис. 2.б. Предполагаем, что <tex>R_i</tex> уже построено, а <tex>S</tex> строится по тому же алгоритму, что и <tex>R</tex>, значит, возможно построить <tex>\mathrm{R_{i+1}} = R_iS</tex>
 +
# Выражение имеет вид <tex>R_i^*</tex>. Используем автомат, представленный на рис. 2.в.
  
[[Файл:RegToAut.png|300px|thumb|right]]
+
{| cellpadding="3"
 +
|[[Файл:RegToAut.png|250px|thumb|center|рис. 2. Индукционный переход преобразования регулярного выражения в НКА]]
 +
|}
  
# Данное выражение имеет вид R|S для некоторых подвыражений R и S. Тогда ему соответствует автомат, представленный на рис. a.
+
===Пример===
# Выражение имеет вид RS. Автомат для этой конкатенации представлен на рис. b.
 
# Выражение имеет вид R* для некоторого подвыражения R. Используем автомат, представленный на рис. c.
 
  
===Пример===
+
Задача: Преобразовать регулярное выражение <tex>(0|1)^*1(0|1)</tex> в ДКА.
 +
 
 +
{| class = "wikitable"
 +
!Регулярное выражение!!Автомат
 +
|-align="center"
 +
|Преобразуем регулярное выражение <tex>(0|1)^*1(0|1)</tex> в <tex>\varepsilon</tex>-НКА. Построим сначала автомат для <tex>0|1</tex>. Это выражение имеет вид <tex>R|S</tex>.
 +
| style="background-color:white;" | [[Файл:0+1.png|280px|thumb]]
 +
|-align="center"
 +
|Далее считаем, что <tex>(0|1)</tex> это подвыражение вида <tex>R</tex>, и строим выражение <tex>(0|1)^*</tex>.
 +
| style="background-color:white;" | [[Файл:(0+1)star.png|280px|thumb]]
 +
|-align="center"
 +
|Выражение <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|280px|thumb]]
 +
|-align="center"
 +
|Удалим <tex>\varepsilon</tex>-переходы, согласно алгоритму из[[Автоматы с eps-переходами. Eps-замыкание | статьи]], получим НКА.
 +
| style="background-color:white;" | [[Файл:removeEps.png|280px|thumb]]
 +
|-align="center"
 +
|Преобразуем НКА в ДКА по [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | алгоритму Томпсона]].
 +
| style="background-color:white;" | [[Файл:minDKA.png|280px|thumb]]
 +
|-align="center"
 +
|}
  
Преобразовать регулярное выражение (0|1)*1(0|1) в ДКА.
+
==Преобразование ДКА в регулярное выражение==
  
# Преобразуем регулярное выражение (0|1)*1(0|1) в ε-НКА. Построим сначала автомат для 0|1. Это выражение имеет вид R|S. Далее считаем, что (0|1) это подвыражение вида R, и строим выражение (0|1)*. Выражение (0|1)*1 имеет вид RS, (0|1)*1(0|1) имеет тот же вид.
+
===Алгебраический метод Бжозовского===
# Удалим ε-переходы, согласно алгоритму из[[Автоматы с eps-переходами. Eps-замыкание | статьи]], получим НКА:
 
#Преобразуем НКА в ДКА по [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | алгоритму Томпсона]] и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) | минимизируем ДКА]].
 
  
=Преобразование ДКА в регулярное выражение=
+
При преобразовании ДКА в регулярное выражение создается система регулярных выражений для каждого состояния в ДКА, а затем она решается для регулярных выражений <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>\varepsilon</tex>. Это приводит к системе уравнений вида:
==Алгебраический метод Бжозовского==
 
Создадим систему регулярных выражений для каждого состояния в ДКА, а затем решим систему для регулярных выражений <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>
Строка 41: Строка 62:
 
</tex>
 
</tex>
  
где <tex>a_x</tex> = если нет перехода от <tex>R_i</tex> к <tex>R_j</tex>.
+
где <tex>a_x</tex> = <tex>\varnothing</tex> если нет перехода от <tex>R_i</tex> к <tex>R_j</tex>.
Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся теоремой Ардена:
+
Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого можно воспользоваться теоремой Ардена:
  
Уравнение вида R = Q + RP, где P <tex>\ne \varepsilon</tex>, имеет решение R = QP*.
+
Уравнение вида <tex>R = Q + RP</tex>, где <tex>P \ne \varepsilon</tex>, имеет решение <tex>R = QP^*</tex>.
  
 
===Пример===
 
===Пример===
Строка 50: Строка 71:
 
[[Файл:AutToReg.png|400px|thumb|right]]
 
[[Файл:AutToReg.png|400px|thumb|right]]
  
Найти: Регулярное выражение, удовлетворяющее данному ДКА.
+
Задача: Построить регулярное выражение, удовлетворяющее данному ДКА.
  
 
Решение:
 
Решение:
Строка 78: Строка 99:
  
 
<tex>R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)</tex>
 
<tex>R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)</tex>
 +
 +
==Источники информации==
 +
 +
* ''John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman'' «Introduction to Automata Theory, Languages, and Computation», 2/E
 +
* ''Christoph Neumann'' «Converting Deterministic Finite Automata to Regular Expressions»

Текущая версия на 13:53, 8 января 2021

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

Чтобы преобразовать регулярное выражение в ДКА, нужно:

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

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

Преобразование проводится структурной индукцией по выражению [math]R[/math], следуя рекурсивному определению регулярных выражений. Необходимо рекурсивно "спуститься" вглубь языка [math]L(R)[/math], дойдя до нулевого уровня - [math]R_0[/math]. Автоматы, распознающие [math]L(R_0)[/math] представлены на рис. 1, это базис.

рис. 1. a. [math]\varepsilon[/math] б. [math]\varnothing[/math] в. [math]a[/math]

Далее строится выражение [math]\mathrm{R_{i+1}}[/math], пока [math]\mathrm{R_{i}} \ne R[/math] следующим образом:

  1. Выражение имеет вид [math]R_i|S[/math], для некоторых выражений [math]R_i[/math] и [math]S[/math]. Тогда ему соответствует автомат, представленный на рис. 2.a. Предполагаем, что [math]R_i[/math] уже построено, а [math]S[/math] строится по тому же алгоритму, что и [math]R[/math], значит, возможно построить [math]\mathrm{R_{i+1}} = R_i|S[/math]
  2. Выражение имеет вид [math]R_iS[/math]. Автомат для этой конкатенации представлен на рис. 2.б. Предполагаем, что [math]R_i[/math] уже построено, а [math]S[/math] строится по тому же алгоритму, что и [math]R[/math], значит, возможно построить [math]\mathrm{R_{i+1}} = R_iS[/math]
  3. Выражение имеет вид [math]R_i^*[/math]. Используем автомат, представленный на рис. 2.в.
рис. 2. Индукционный переход преобразования регулярного выражения в НКА

Пример

Задача: Преобразовать регулярное выражение [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]\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]\varnothing[/math] если нет перехода от [math]R_i[/math] к [math]R_j[/math]. Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого можно воспользоваться теоремой Ардена:

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

Пример

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]

Источники информации

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman «Introduction to Automata Theory, Languages, and Computation», 2/E
  • Christoph Neumann «Converting Deterministic Finite Automata to Regular Expressions»