78
правок
Изменения
→Преобразование ДКА в регулярное выражение с помощью алгебраического метода Бжозовского.
3) Преобразуем НКА в ДКА и минимизируем ДКА:
=Преобразование ДКА в регулярное выражение с помощью алгебраического метода ===Алгебраический метод Бжозовского.==
Создадим систему регулярных выражений для каждого состояния в ДКА, а затем решим систему для регулярных выражений <tex>R_i</tex>, связанных с терминальным состояниями <tex>q_i</tex>. Строим уравнения следующим образом: для каждого состояния <tex>q_i</tex> уравнение <tex>R_i</tex> является объединением переходов, ведущих в это состояние. Переход a из <tex>q_i</tex> в <tex>q_j</tex> обозначим за <tex>aR_i</tex>. Если <tex>q_i</tex> - терминальное состояние, то добавим в <tex>R_i</tex> <tex>\ne \varepsilon</tex>. Это приводит к системе уравнений вида:
