Изменения

Построение проводится структурной индукцией по выражению <tex>R</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]]. Необходимо рекурсивно спуститься вглубь языка <tex>L(R)</tex>, дойдя до нулевого уровня - <tex>R_0</tex>. Автоматы, распознающие <tex>L(R_0)</tex> представлены на рис. 1, это базис. Далее строится выражение <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>