私は決定論と非決定論の意味に少し苦労しています。オートマトンに関しては違いがわかりますが、次の答えを見つけることができないようです: NFA から DFA への変換は決定論的ですか?
同じ正規言語に対して複数の DFA を構築できる場合、NFA から DFA への変換の結果は一意ではないということですか? したがって、非決定論的アルゴリズムですか？
皆さんが提供できる情報があれば幸いです。
前もって感謝します！
1 に答える
3
ここでは、2 つの異なる概念が使用されています。まず、同じ NFA に相当する多くの異なる DFA が存在する可能性があることは正しいです。これは、すべてが互いに同等である多くの NFA が存在する可能性があるのと同じです。
独立して、NFA を DFA に変換するためのアルゴリズムがいくつかあります。形式言語のほとんどの入門クラスで教えられている標準アルゴリズムは、サブセット構成 (パワーセット構成とも呼ばれます) です。そのアルゴリズムは決定論的です。NFA を DFA に変換するには特定の手順に従う必要があるため、同じ NFA をフィードするたびに、常に同じ DFA が返されます。おそらく、NFA を DFA に変換するための非決定論的アルゴリズムを使用することができます。この場合、アルゴリズムは出力として多くの異なる DFA の 1 つを生成する可能性がありますが、私の知る限り、この種の有名なアルゴリズムはありません。
お役に立てれば！
于 2014-08-29T18:50:33.947 に答える