78
правок
Изменения
→Преобразование регулярного выражения в \varepsilon-НКА.
[[Файл:RegToAut.png|280px|thumb|right|рис. 1. "Виды выражений"]]
В построении регулярных выражений используются константы(<tex>\varepsilon</tex> и ∅) и переменные для обозначения языков, и операторы для обозначения объединения(<tex>|</tex>), конкатенации и [[Основные определения, связанные со строками#Формальные языки | замыкания Клини]](<tex>^*</tex>). Регулярные выражения можно определить рекурсивно. Для каждого регулярного выражения <tex>E</tex> описывается представленный им язык, который обозначается через <tex>L(E)</tex>.
Чтобы преобразовать регулярное выражения в <tex>\varepsilon</tex>-НКА, предполагается, что <tex>L = L(R)</tex> для регулярного выражения <tex>R</tex>. Построение проводится структурной индукцией по выражению <tex>R</tex>. Три части индукции представлены на рис. 1. Произведем разбиение данного регулярного выражения на подвыражения. Возможны четыре случая.
