Изменения

[[Файл:базис.png|150px|thumb|right|рис. 1. Автоматы, распознающие регулярные языки нулевого уровня a. <tex>\varepsilon</tex> б. <tex>\varnothing</tex> в. <tex>a</tex>]] [[Файл:RegToAut.png|280px200px|thumb|right|рис. 12. Индуктивный шаг преобразования регулярного выражения в НКА]]

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

# Выражение имеет вид <tex>R_i|S</tex>, для некоторых выражений <tex>R_i</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 12.a. Если L(S) - язык ненулевого уровня, то необходимо повторить те же шаги, что и при построении <tex>R</tex>.# Выражение имеет вид <tex>R_iS</tex>. Автомат для этой конкатенации представлен на рис. 12.б. Если L(S) - язык ненулевого уровня, то необходимо повторить те же шаги, что и при построении <tex>R</tex>. # Выражение имеет вид <tex>R_i^*</tex>. Используем автомат, представленный на рис. 12.в.