Это правильный график NFA?

Question

Задача: собрать NFA из заданного регулярного выражения.

Я решил перенести некоторые из моих старых программ на GitHub.Конкретно проблемы, касающиеся теории формальных языков.После тестирования кода у меня был такой результат, и я не могу точно сказать, является ли это неправильным или правильным выводом.Это вроде как выглядит правильно, но не то, что выдаст алгоритм Томпсона.Также эти маленькие петли выглядят подозрительно.Они в основном ничего не делают, хотя.

Answer 1

Моя реализация C # алгоритма Бжозовского для минимизации DFA дает DFA ниже.(0) - начальное состояние, (2) и (3) - конечные состояния.

Answer 2

Определенно неверно.

Эпсилон-циклы выглядят для меня как ошибка в обработке оператора объединения.Должен быть эпсилон-переход из каждого конечного состояния в объединении в новое конечное состояние, поэтому я предполагаю, что вы перепутали ссылки на эпсилон.Я не уверен, как вы получите правильный эпсилон-переход на a в одном случае и b в другом, так что, возможно, ошибка более сложная.

Вы правы в этомВ этом случае в эпсилон-цикле нет никакого вреда.Но вполне возможно, что отсутствие эпсилон-ссылки от конца ветви объединения до конечного состояния объединения вызовет проблему с (a*|b) или (a|b*).Возможно, один из них действительно распознает (a|b)+.

Кроме того, ваша реализация Kleene star не допускает нулевых повторений.То, что у вас есть, это (a|b)+, а не (a|b)*, потому что нет эпсилон-перехода из начального состояния в состояние подконструкции звезды.