私はグーグルを検索しましたが、多くのページで、最小化されたDFAのデッド状態またはトラップ状態が削除されていることが示されています。私の質問は、トランジションが定義されていない場合、どうすればDFAのままでいられるかということです。それで、あなたは人々を何と言いますか？
9076 次
3 に答える
7
最小限の DFA でさえ、dead ステートを含める必要があります。それ以外の場合は、(a) DFA ではないか、(b) 非最小の対応する言語と同じ言語を受け入れていません。たとえば、アルファベット {a, b} に対する言語 {a} の最小限の DFA には、3 つの状態が必要です。他に何か見たら拒否する受け入れ状態。そして、受け入れ状態でabまたは何かを見た場合に行く死んだ状態。
最小限の DFA からデッド ステートを省略したという話は聞いたことがありません。冒涜！
于 2012-02-04T13:52:58.337 に答える
0
@PrashantBhardwaj ：それを含めるとDFAが完了するため、それ（デッドステートと対応するデッドムーブ）を含める必要があると思います。
それでも、質問は未回答ですか？最後に、それを含めるべきかどうか。誰でもそれを証明できますか？
于 2015-09-07T05:37:37.940 に答える