私は正規表現を与えられました、そして私はそれをNFAそしてDFAに隠蔽することになっています。正規表現は次のとおりです。
a（b | c）* a | aac * b
次に、トムソンのアルゴリズムを使用してこれをNFAにカバーしました。
これがDFAです。
誰かが私が間違っているか正しいかを私に知らせてください。
1 に答える
4
これは宿題である可能性が非常に高いので、完全に正しい解決策を提供することを躊躇します。
NFAは正しいように見えますが、必要ではないがその正確性に悪影響を及ぼさない余分な状態がたくさんあります。（一見すると、11の状態を削除できるように見えます。）
ただし、DFAは正しくありません。これは、分岐して文字列のいずれかの条件の処理を開始するときに、後でそれらを再結合するためです。これにより、受け入れられた文字列照合からパスをa(b|c)*a取得し、別の文字列を取得するか、ノードまたはに移動することがbできます。次に、式と一致しなくても、この文字列を受け入れます。c15,1711
あなたがする必要があるのは基本的にこれが起こらないようにすることです。他にご不明な点がございましたら、お気軽にお問い合わせください。
受け入れるべきであると受け入れるべきではないことがわかっているテスト文字列のリストを作成し、それらをトレースして、オートマトンが正しい（受け入れまたは拒否）状態で終了することを確認することを強くお勧めします。
于 2011-03-05T18:18:37.723 に答える