Шаги по созданию NFA из регулярного выражения
У меня "есть проблемы", описывающие каждый шаг ". при создании NFA из регулярного выражения. Вопрос в следующем:
Преобразуйте следующее регулярное выражение в недетерминированный конечный автомат (NFA), четко описывающий шаги используемого вами алгоритма: (Б | а) * Ь (а | б)
Я сделал простую машину с тремя состояниями, но это очень сильно зависит от интуиции. Это вопрос из прошлого экзамена, написанного моим лектором, который также написал следующее объяснение алгоритма Томпсона:http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html
Кто-нибудь может прояснить, как «четко описать каждый шаг»? Это просто набор базовых правил, а не алгоритм с шагами, которым нужно следовать.
Может быть, есть алгоритм, который я где-то замалчивал, но до сих пор я только что создал их с обоснованным предположением.