（ab u aab u aba）*をNFAに変換するにはどうすればよいですか？

Question

（AB U AAB U ABA）*

私はそれをやったが、私はその正しさにいくつかのフィードバックたいと思います：それは正しい場合

を：我々は、任意の*（AB U AAB U ABA）簡素化することができますさらに？

そうでない場合：私は何を欠席しましたか？

EDIT：私は3つの最終状態すべてから初期状態に戻っていないようですが、私は新しい移行状態が必要です。これは初期遷移であり、最終状態はe-transitionで古い初期状態になります。 （クレーネスタールール）。

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（bu ab u ba））*しかし、それは必ずしも役立つわけではありません。私はあなたのDFAは、あなたが思っているほど多くの州を必要としないと思っています。

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