Изменения

Чтобы преобразовать регулярное выражение в НКА, предполагается, что Построение проводится структурной индукцией по выражению <tex>L = L(R)</tex> для , следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярного выражениярегулярных выражений]] . Рекурсивно идем вглубь выражения, пока не дойдем до нулевого уровня. Когда <tex>RR_i</tex>. Построение проводится структурной индукцией по выражению содержит один символ, несложно построить автомат, распознающий <tex>L(R)</tex>, следуя рекурсивному определению [[Регулярные языки: два определения и их эквивалентность| регулярных выражений]] - . Далее необходимо построить выражение <tex> \mathrm{R_{iR_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>a</tex>, где <tex>a ∈ Σ</tex>. Несложно построить автомат, распознающий <tex>L(R)</tex>. Индукция: Пусть каждое регулярное выражение длины меньше <tex>k > 1</tex> соответствует некоторому регулярному языку. Рассматривается выражение <tex>R_k</tex> длины <tex>k</tex>. Три части индукции представлены на рис. 1: # Выражение имеет вид <tex>RR_i|S</tex>, для некоторых выражений <tex>RR_i</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 1.a.# Выражение имеет вид <tex>RSR_iS</tex>. Автомат для этой конкатенации представлен на рис. 1.б. # Выражение имеет вид <tex>RR_i^*</tex> для некоторого подвыражения <tex>R</tex>. Используем автомат, представленный на рис. 1.в.# Выражение имеет вид <tex>(R)</tex> для некоторого подвыражения <tex>R</tex>. Автомат для <tex>R</tex> может быть автоматом и для <tex>(R)</tex>, поскольку скобки не влияют на язык, задаваемый выражением.