DFA に対する NFA の利点: 表現はより少ないメモリを使用します。
NFA と比較した NFA の欠点: 答えに到達するのが遅い。
他にメリットやデメリットはありますか？
2541 次
2 に答える
8
私はあなたが頭の中で主なトレードオフをかなり釘付けにしたと思います。NFAは、O（n）空間でO（2 n ）の異なる構成をエンコードできるため、メモリ効率が高くなりますが、同じ言語のDFAは指数空間を使用する場合があります。NFAの更新が遅いことも同様に正しいです。NFAをシミュレートするためのほとんどのアルゴリズムは、状態遷移（nは状態の数）を計算するのにO（n）時間かかるのに対し、DFAの場合はO（1）時間かかります。
2つの間に他のいくつかの違いがあります。手始めに、状態とシンボルの各ペアに対して1つの遷移があるため、DFAは通常エンコードが簡単です。これは、遷移表の多次元配列に自然に役立ちます。対照的に、NFA（またはさらに悪いことにε-NFA）は、どの状態でも多数の遷移が存在する可能性があるため、通常、より複雑な表現を必要とします。ただし、NFAには、複雑な構造からオートマトンへの多くの変換がNFAを使用すると簡単になるという利点があります。たとえば、正規表現から一致するオートマトンを標準的に構築すると、DFAではなくε-NFAが生成されます。これは、変換がより小さなε-NFAを再帰的に構築し、ε-movesを使用してそれらを結合することによって最もよく表現されるためです。それ' 正規表現をDFAに直接変換することは可能ですが、変換するのはかなり困難です。同様に、LR（k）パーサーを生成するための多くのアルゴリズムは、ハンドル認識オートマトンがDFAではなくNFAの観点からどのように機能するかを調べることで、より直感的に動機付けられます（ただし、これらのパーサーを生成するためのほとんどのアルゴリズムは、NFAではなくDFAに直接送信されます） ）。
お役に立てれば！
于 2011-02-04T03:28:36.087 に答える
1
NFA表現はよりコンパクトですが、DFAのシミュレーションはより簡単です。多くの場合、NFAがDFAに縮小されると、指数関数的なサイズの増加があります
于 2011-02-04T03:29:33.097 に答える