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