78
правок
Изменения
→Преобразование регулярного выражения в ДКА
==Алгоритм==
[[Файл:RegToAut.png|300px|thumb|right|рис. 1]]
# Преобразуем регулярное выражение в <tex>\varepsilon</tex>-НКА.
Виды выражений:
# Данное выражение имеет вид <tex>R|S </tex> для некоторых подвыражений <tex>R </tex> и <tex>S</tex>. Тогда ему соответствует автомат, представленный на рис. 1. a.# Выражение имеет вид <tex>RS</tex>. Автомат для этой конкатенации представлен на рис. 1. b.# Выражение имеет вид <tex>R^* </tex> для некоторого подвыражения R. Используем автомат, представленный на рис. 1. c.
===Пример===
Преобразовать регулярное выражение <tex>(0|1)^*1(0|1) </tex> в ДКА.
{| class = "wikitable"
