Как конвертировать (ab u aab u aba) * в NFA?

Question

(ab u aab u aba) *

Я сделал это, но хотел бы получить отзыв о его правильности:

Если это правильно: Можем ли мы упростить (ab u aab u aba) * дальше?

Если нет: то, что я пропустил?

РЕДАКТИРОВАТЬ: Кажется, мне не хватает электронных переходов из всех трех конечных состояний обратно в начальное состояние, и мне нужно новое состояние, начальное и конечное, которое перейдет в старое начальное состояние при электронном переходе. (Правило Клини Стар).

P.S. Можем ли мы также упростить (a u b)*aabab и (a u b)*a(a u b)(a u b)(a u b)(a u b).

Причина, по которой я спрашиваю, потому что, если нет способа упростить / минимизировать, это будет смехотворно длинный DFA ...

Answer 1

Я вижу небольшое упрощение вашего первого случая в том, что вы можете написать его как (a (b u ab u ba)) *, но это не обязательно поможет. Я бы все-таки предположил, что вашему DFA не понадобится столько штатов, сколько вы думаете.

В обоих последних случаях потребуются DFA с 32 состояниями для отслеживания последних 5 прочитанных символов. Разница в том, что второй DFA имеет только одно конечное состояние, в то время как третий DFA имеет 16.