==Преобразование регулярного выражения в ДКА==
==Алгоритм==Чтобы преобразовать [[Регулярные языки: два определения и их эквивалентность| регулярное выражение]] в [[Детерминированные конечные автоматы|ДКА]], нужно:
# Преобразуем Преобразовать регулярное выражение в ε[[Недетерминированные конечные автоматы|НКА]] с <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|800px250px|thumb|rightcenter|рис. 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>\ne \varepsilon</tex>. Это приводит к системе уравнений вида:
<tex>
</tex>
где <tex>a_x</tex> = ∅ <tex>\varnothing</tex> если нет перехода от <tex>R_i</tex> к <tex>R_j</tex>.Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся можно воспользоваться теоремой Ардена:
Уравнение вида <tex>R = Q + RP</tex>, где P <tex>P \ne \varepsilon</tex>, имеет решение <tex>R = QP^*</tex>.
===Пример===
[[Файл:AutToReg.png|400px|thumb|right]]
НайтиЗадача: Регулярное Построить регулярное выражение, удовлетворяющее данному ДКА.
Решение:
<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»
