Изменения

1) Преобразовать # Преобразуем регулярное выражение в ε-НКА. Будем пользоваться следующим правилом:1# Устраним ε-переходы.[[Автоматы с eps-переходами. Для регулярного выражения A|B можем построить следующий КА:Eps-замыкание]] # Построим по НКА эквивалентное ДКА по алгоритму Томпсона.[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]

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