78
правок
Изменения
→Преобразование регулярного выражения в ДКА
==Алгоритм==
[[Файл:RegToAut.png|300px|thumb|right]] # Преобразуем регулярное выражение в ε<tex>\varepsilon</tex>-НКА.# [[Автоматы с eps-переходами. Eps-замыкание | Устраним ε<tex>\varepsilon</tex>-переходы.]]
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | Построим по НКА эквивалентное ДКА по алгоритму Томпсона.]]
===Преобразование регулярного выражения в ε-НКА.===
подвыражениям.
!Регулярное выражение!!Автомат
|-align="center"
|Преобразуем регулярное выражение <tex>(0|1)^*1(0|1)</tex> в ε<tex>\varepsilon</tex>-НКА. Построим сначала автомат для <tex>0|1</tex>. Это выражение имеет вид <tex>R|S</tex>.| style="background-color:white;" | [[Файл:0+1.png|200px|thumb]]
|-align="center"
|Далее считаем, что <tex>(0|1)</tex> это подвыражение вида R, и строим выражение <tex>(0|1)^*</tex>.| style="background-color:white;" | [[Файл:(0+1)star.png|200px|thumb]]
|-align="center"
|Выражение <tex>(0|1)^*1</tex> имеет вид RS, <tex>(0|1)^*1(0|1)</tex> имеет тот же вид.| style="background-color:white;" | [[Файл:(0+1)star1(0+1).png|200px|thumb]]
|-align="center"
|Удалим ε<tex>\varepsilon</tex>-переходы, согласно алгоритму из[[Автоматы с eps-переходами. Eps-замыкание | статьи]], получим НКА.| style="background-color:white;" | [[Файл:removeEps.png|200px|thumb]]
|-align="center"
|Преобразуем НКА в ДКА по [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | алгоритму Томпсона]] и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) | минимизируем ДКА]]
| style="background-color:white;" | [[Файл:minDKA.png|200px|thumb]]
|-align="center"
|}
