78
правок
Изменения
→Преобразование регулярного выражения в НКА
[[Файл:RegToAut.png|200px|thumb|right|рис. 2. Индуктивный шаг преобразования регулярного выражения в НКА]]
Построение проводится структурной индукцией по выражению <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+1) }} \ne R</tex>:
# Выражение имеет вид <tex>R_i|S</tex>, для некоторых выражений <tex>R_i</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 2.a. Если <tex>L(S)</tex> - язык ненулевого уровня, то необходимо повторить те же шаги, что и при преобразовании <tex>R</tex>.
