78
правок
Изменения
→Преобразование регулярного выражения в НКА
[[Файл:RegToAut.png|280px|thumb|right|рис. 1. Индуктивный шаг преобразования регулярного выражения в НКА]]
Построение проводится структурной индукцией по выражению <tex>R</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]]. Рекурсивно идем Необходимо рекурсивно спуститься вглубь выражения, пока не дойдем доходя до нулевого уровня. Когда <tex>R_i</tex> содержит один символ, несложно построить автомат, распознающий <tex>L(R)</tex>. Далее необходимо построить строится выражение <tex>R_i+1</tex>, пока <tex>R_i+1 /ne R</tex>:
# Выражение имеет вид <tex>R_i|S</tex>, для некоторых выражений <tex>R_i</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 1.a.
