78
правок
Изменения
→Преобразование регулярного выражения в ДКА
=Преобразование регулярного выражения в ДКА= ==Алгоритм==
# Преобразуем регулярное выражение в ε-НКА.
# Устраним ε-переходы.[[Автоматы с eps-переходами. Eps-замыкание| Устраним ε-переходы.]]# Построим по НКА эквивалентное ДКА по алгоритму Томпсона.[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона| Построим по НКА эквивалентное ДКА по алгоритму Томпсона.]]
===Преобразование регулярного выражения в ε-НКА.===
# Преобразуем регулярное выражение (0|1)*1(0|1) в ε-НКА. Построим сначала автомат для 0|1. Это выражение имеет вид R|S. Далее считаем, что (0|1) это подвыражение вида R, и строим выражение (0|1)*. Выражение (0|1)*1 имеет вид RS, (0|1)*1(0|1) имеет тот же вид.
# Удалим ε-переходы, согласно алгоритму из статьи[[Автоматы с eps-переходами. Eps-замыкание| статьи]], получим НКА:#Преобразуем НКА в ДКА по алгоритму Томпсона[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона | алгоритму Томпсона]] и минимизируем ДКА [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))| минимизируем ДКА]].
=Преобразование ДКА в регулярное выражение=
