78
правок
Изменения
→Источники информации
===Преобразование регулярного выражения в НКА===
# Выражение имеет вид <tex>R_i|S</tex>, для некоторых выражений <tex>R_i</tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 2.a. Предполагаем, что <tex>R_i</tex> уже построено, а <tex>S</tex> строится по тому же алгоритму, что и <tex>R</tex>, значит, возможно построить <tex>\mathrm{R_{i+1}} = R_i|S</tex>
# Выражение имеет вид <tex>R_iS</tex>. Автомат для этой конкатенации представлен на рис. 2.б. Предполагаем, что <tex>R_i</tex> уже построено, а <tex>S</tex> строится по тому же алгоритму, что и <tex>R</tex>, значит, возможно построить <tex>\mathrm{R_{i+1}} = R_iS</tex>
# Выражение имеет вид <tex>R_i^*</tex>. Используем автомат, представленный на рис. 2.в.
{| cellpadding="3"
|[[Файл:RegToAut.png|250px|thumb|center|рис. 2. Индукционный переход преобразования регулярного выражения в НКА]]
|}
===Пример===
<tex>R = R_1 + R_4= (ab+ba)^* (\varepsilon + (aa+bb) (a+b)^*)</tex>
==Источники информации==
