Просмотр исходного текста страницы Преобразование регулярного выражения в ДКА

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

Чтобы преобразовать [[Регулярные языки: два определения и их эквивалентность| регулярное выражение]] в [[Детерминированные конечные автоматы|ДКА]], нужно:

# Преобразовать регулярное выражение в [[Недетерминированные конечные автоматы|НКА]] с <tex>\varepsilon</tex>-переходами.
# Устранить [[Автоматы с 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.в.

{| cellpadding="3"
|[[Файл:RegToAut.png|250px|thumb|center|рис. 2. Индукционный переход преобразования регулярного выражения в НКА]]
|}

===Пример===

Задача: Преобразовать регулярное выражение <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"
|}

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

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

При преобразовании ДКА в регулярное выражение создается система регулярных выражений для каждого состояния в ДКА, а затем она решается для регулярных выражений <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>
\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}
</tex>

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

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

===Пример===

[[Файл:AutToReg.png|400px|thumb|right]]

Задача: Построить регулярное выражение, удовлетворяющее данному ДКА.

Решение:

<tex>
\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}
</tex>

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

<tex>R_1 = \varepsilon + abR_1 + baR_1 = \varepsilon + R_1(ab+ba)</tex>

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

<tex>R_1=(ab+ba)^*</tex>

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

<tex>R_4=R_1(aa+bb)+R_4(a+b)=R_1(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»

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]