0

正規表現の非決定論的有限状態オートマトンへの変換について質問があります。

（a * | b *）*をNFAに変換します。私の試みは次のとおりです。

ここに画像の説明を入力してください

私は完全にマークから外れていますか？またはいくらかそこに？

NBE=>ε

4

1 に答える 1

3

あなたのNFAはと同じ言語に一致する(a*|b*)*ので、答えは正しいです。

ただし、同じ言語に一致するNFAは多数あり、あなたの場合、少なくとも3つのイプシロン矢印を削除することが可能です。それでも、それはあなたの提案よりも正確ではありません。

セマンティクスを変更せずに、正規表現(a*|b*)*を簡略化することもできます。たとえば、はと(a|b)*同等(a*|b*)*です。そして、あなたがそれについて考えるならば、FAはこれと同じくらい単純である可能性があります：

（a | b）*に相当する有限オートマトン

于 2011-05-09T17:37:33.380 に答える