Чтобы преобразовать [[Регулярные языки: два определения и их эквивалентность| регулярное выражение]] в [[Детерминированные конечные автоматы|ДКА]], нужно:
# Преобразовать регулярное выражение в[[Недетерминированные конечные автоматы|НКА]] с <tex>\varepsilon</tex>-переходами.
# Устранить [[Автоматы с eps-переходами. Eps-замыкание | <tex>\varepsilon</tex>-переходы.]]
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | Построить]] по НКА эквивалентный ДКА.
===Преобразование регулярного выражения в <tex>\varepsilon</tex>-НКА===
[[Файл:RegToAut.png|280px|thumb|right|рис. 1. "Виды выражений"Индуктивный шаг преобразования регулярного выражения в НКА]]
В построении регулярных выражений используются константы(Чтобы преобразовать регулярное выражение в НКА, предполагается, что <tex>\varepsilonL = L(R)</tex> и ∅) и переменные для обозначения языков, и операторы для обозначения объединения(<tex>|</tex>), конкатенации и [[Основные Регулярные языки: два определения, связанные со строками#Формальные языки и их эквивалентность| замыкания Клинирегулярного выражения]](<tex>^*R</tex>). Регулярные выражения можно определить рекурсивно. Для каждого регулярного выражения Построение проводится структурной индукцией по выражению <tex>ER</tex> описывается представленный им язык, который обозначается через следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]] - <tex>L(E)\mathrm{R_{i+1}} = \mathrm{R_i} \cup \left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in \mathrm{R_i}\right\} </tex>.
Чтобы преобразовать регулярное выражения в Базис: <tex>R</tex> содержит один символ. В этом случае <tex>R</tex> имеет вид: <tex>\varepsilon</tex>-НКА, предполагается, что ∅ или <tex>L = L(R)a</tex> для регулярного выражения , где <tex>Ra ∈ Σ</tex>. Построение проводится структурной индукцией по выражению Несложно построить автомат, распознающий <tex>L(R)</tex>. Три части индукции представлены на рис. 1. Произведем разбиение данного регулярного выражения на подвыражения. Возможны четыре случая.
Виды выраженийИндукция: Пусть каждое регулярное выражение длины меньше <tex>k > 1</tex> соответствует некоторому регулярному языку. Рассматривается выражение <tex>R_k</tex> длины <tex>k</tex>. Три части индукции представлены на рис. 1:
# Данное выражение Выражение имеет вид <tex>R|S</tex> , для некоторых подвыражений выражений <tex>R</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 1.a.
# Выражение имеет вид <tex>RS</tex>. Автомат для этой конкатенации представлен на рис. 1.б.
# Выражение имеет вид <tex>R^*</tex> для некоторого подвыражения <tex>R</tex>. Используем автомат, представленный на рис. 1.в.
