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