Это правильный график NFA?
Задача: Построить NFA из заданного регулярного выражения.
Я решил перенести некоторые из моих старых программ на GitHub. Конкретно проблемы, касающиеся теории формальных языков. После тестирования кода у меня был такой результат, и я не могу точно сказать, является ли это неправильным или правильным выводом. Это вроде как выглядит правильно, но не то, что мог бы выдать алгоритм Томпсона. Также эти маленькие петли выглядят подозрительно. Они в основном ничего не делают, хотя. 
2 ответа
Определенно неправильно.
Циклы epsilon-self выглядят для меня как ошибка в обработке оператора объединения. Должен быть эпсилон-переход из каждого конечного состояния в объединении в новое конечное состояние, поэтому я предполагаю, что вы перепутали ссылки на эпсилон. Я не уверен, как вы в конечном итоге с правильным переходом эпсилон на a в одном случае и b в другом, так что, возможно, ошибка более сложная.
Вы правы в том, что в этом случае эпсилон-цикл не причинит вреда. Но вполне возможно, что отсутствие эпсилон-связи между концом союза и конечным государством союза вызовет проблему с (a*|b) или же (a|b*), Один из них может на самом деле признать (a|b)+,
Кроме того, ваша реализация Kleene star не допускает нулевых повторений. Что у вас есть (a|b)+не (a|b)*потому что нет эпсилон-перехода из начального состояния в состояние подконструкции звезды.
Моя реализация C# алгоритма Бжозовского для минимизации DFA дает DFA ниже. (0) - начальное состояние, (2) и (3) - конечные состояния.
