78
правок
Изменения
→Пример
===Пример===
[[Файл:0+1.png|200px|thumb|рис. 2.1]] [[Файл:(0+1)star.png|250px|thumb|рис. 2.2]] [[Файл:(0+1)star1(0+1).png|200px|thumb|left|рис. 2.3]] [[Файл:removeEps.png|200px|thumb|left| рис. 3]] [[Файл:minDKA.png|200px|thumb|left|рис. 4]]
Преобразовать регулярное выражение (0|1)*1(0|1) в ДКА.
# Преобразуем регулярное выражение (0|1)*1(0|1) в ε-НКА. Построим сначала автомат для 0|1(рис. 2.1). Это выражение имеет вид R|S. Далее считаем, что (0|1) это подвыражение вида R, и строим выражение (0|1)*(рис. 2.2). Выражение (0|1)*1 имеет вид RS, (0|1)*1(0|1) имеет тот же вид(рис. 2.3). # Удалим ε-переходы, согласно алгоритму из[[Автоматы с eps-переходами. Eps-замыкание | статьи]], получим НКА:. (рис. 3)#Преобразуем НКА в ДКА по [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | алгоритму Томпсона]] и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) | минимизируем ДКА]](рис. 4).
=Преобразование ДКА в регулярное выражение=
