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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Преобразование регулярного выражения в НКА)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Источники информации)
 
(не показано 10 промежуточных версий этого же участника)
Строка 9: Строка 9:
 
===Преобразование регулярного выражения в НКА===
 
===Преобразование регулярного выражения в НКА===
  
[[Файл:базис.png|100px|thumb|рис. 1. a. <tex>\varepsilon</tex> б. <tex>\varnothing</tex> в. <tex>a</tex>]]
+
Преобразование проводится структурной индукцией по выражению <tex>R</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]]. Необходимо рекурсивно "спуститься" вглубь языка <tex>L(R)</tex>, дойдя до нулевого уровня - <tex>R_0</tex>. Автоматы, распознающие <tex>L(R_0)</tex> представлены на рис. 1, это базис.
[[Файл:RegToAut.png|200px|thumb|right|рис. 2. Индуктивный переход преобразования регулярного выражения в НКА]]
+
{| cellpadding="3"
 
+
|[[Файл:базис.png|150px|thumb|center|рис. 1. a. <tex>\varepsilon</tex> б. <tex>\varnothing</tex> в. <tex>a</tex>]]
Преобразование проводится структурной индукцией по выражению <tex>R</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]]. Необходимо рекурсивно "спуститься" вглубь языка <tex>L(R)</tex>, дойдя до нулевого уровня - <tex>R_0</tex>. Автоматы, распознающие <tex>L(R_0)</tex> представлены на рис. 1, это базис. Далее строится выражение <tex>\mathrm{R_{i+1}}</tex>, пока <tex>\mathrm{R_{i}} \ne R</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_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_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.в.
 
# Выражение имеет вид <tex>R_i^*</tex>. Используем автомат, представленный на рис. 2.в.
 +
 +
{| cellpadding="3"
 +
|[[Файл:RegToAut.png|250px|thumb|center|рис. 2. Индукционный переход преобразования регулярного выражения в НКА]]
 +
|}
  
 
===Пример===
 
===Пример===
Строка 94: Строка 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>
 
==См. Также==
 
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 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»