regex - (ab u aab u aba)* を NFA に変換するには?

Question

(ab u aab u aba)*

私はそれをしましたが、その正しさについてのフィードバックが欲しいです:

正しければ: (ab u aab u aba)* をさらに単純化できますか?

そうでない場合: 何を見逃しましたか?

編集: 3 つの最終状態すべてから初期状態に戻る e トランジションが欠落しているようです。e トランジションで古い初期状態に移動する初期および最終の新しい状態が必要です。（クリーネスタールール）。

PS と を単純化することもできます(a u b)*aababか(a u b)*a(a u b)(a u b)(a u b)(a u b)。

単純化/最小化する方法がない場合、非常に長いDFAになるため、私が尋ねる理由...

Answer 1

最初のケースを (a(bu ab u ba))* のように書けるという点で少し簡略化できますが、必ずしも役に立ちません。あなたのDFAは、あなたが思っているほど多くの州を必要としないと思います。

後者の場合はどちらも、最後に読み取った 5 文字を追跡するために、32 の状態を持つ DFA が必要になります。違いは、2 番目の DFA には 1 つの最終状態しかないのに対し、3 番目の DFA には 16 の最終状態があることです。