Изменения

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

# Преобразовать регулярное выражение в [[Файл:RegToAutНедетерминированные конечные автоматы|НКА]] с <tex>\varepsilon</tex>-переходами.# Устранить [[Автоматы с eps-переходами.pngEps-замыкание |300px<tex>\varepsilon</tex>-переходы.]]# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона |thumb|right|рис. 1 "Виды выражений"Построить]] по НКА эквивалентный ДКА.

# Преобразуем регулярное выражение ===Преобразование регулярного выражения в <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>\varepsilonmathrm{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"# Данное выражение имеет вид <tex>R|S</tex> для некоторых подвыражений <tex>R</tex> и <tex>S</tex>[[Файл:RegToAut. Тогда ему соответствует автомат, представленный на png|250px|thumb|center|рис. 1.a2.Индукционный переход преобразования регулярного выражения в НКА]]# Выражение имеет вид <tex>RS</tex>. Автомат для этой конкатенации представлен на рис. 1.б. # Выражение имеет вид <tex>R^*</tex> для некоторого подвыражения <tex>R</tex>. Используем автомат, представленный на рис. 1.в.|}

|Преобразуем НКА в ДКА по [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | алгоритму Томпсона]] и [[Минимизация ДКА, алгоритм Хопкрофта (сложность 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>a_x</tex> = ∅ <tex>\varnothing</tex> если нет перехода от <tex>R_i</tex> к <tex>R_j</tex>.Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого воспользуемся можно воспользоваться теоремой Ардена: