Чтобы преобразовать [[Регулярные языки: два определения и их эквивалентность| регулярное выражение]] в [[Детерминированные конечные автоматы|ДКА]], нужно:
# Преобразовать регулярное выражение в [[Недетерминированные конечные автоматы|НКА]] с <tex>\varepsilon</tex>-[[Недетерминированные конечные автоматы|НКА]]переходами.
# Устранить [[Автоматы с eps-переходами. Eps-замыкание | <tex>\varepsilon</tex>-переходы.]]
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | ПостроимПостроить]] по НКА эквивалентный ДКА.
===Преобразование регулярного выражения в <tex>\varepsilon</tex>-НКА===
Преобразование проводится структурной индукцией по выражению <tex>R</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]]. Необходимо рекурсивно "спуститься" вглубь языка <tex>L(R)</tex>, дойдя до нулевого уровня - <tex>R_0</tex>. Автоматы, распознающие <tex>L(R_0)</tex> представлены на рис. 1, это базис.{| cellpadding="3"|[[Файл:RegToAutбазис.png|280px150px|thumb|rightcenter|рис. 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>\varepsilonR_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>ES</tex> описывается представленный им языкстроится по тому же алгоритму, что и <tex>R</tex>, значит, который обозначается через возможно построить <tex>\mathrm{R_{i+1}} = R_iS</tex># Выражение имеет вид <tex>L(E)R_i^*</tex>. Используем автомат, представленный на рис. 2.в.
Чтобы преобразовать регулярное выражения в <tex>\varepsilon</tex>-НКА, предполагается, что <tex>L {| cellpadding= L(R)</tex> для регулярного выражения <tex>R</tex>"3"|[[Файл:RegToAut. Построение проводится структурной индукцией по выражению <tex>R</tex>. Три части индукции представлены на png|250px|thumb|center|рис. 12. Произведем разбиение данного Индукционный переход преобразования регулярного выражения на подвыражения. Возможны четыре случая. в НКА]] Виды выражений: # Данное выражение имеет вид <tex>R|S</tex> для некоторых подвыражений <tex>R</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 1.a.# Выражение имеет вид <tex>RS</tex>. Автомат для этой конкатенации представлен на рис. 1.б. # Выражение имеет вид <tex>R^*</tex> для некоторого подвыражения <tex>R</tex>. Используем автомат, представленный на рис. 1.в.# Выражение имеет вид <tex>(R)</tex> для некоторого подвыражения <tex>R</tex>. Автомат для <tex>R</tex> может быть автоматом и для <tex>(R)</tex>, поскольку скобки не влияют на язык, задаваемый выражением.}
===Пример===
</tex>
где <tex>a_x</tex> = ∅ <tex>\varnothing</tex> если нет перехода от <tex>R_i</tex> к <tex>R_j</tex>.
Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого можно воспользоваться теоремой Ардена:
<tex>R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)</tex>
==См. Также==
==Источники информации==
