NFAの賛否両論はDFAと比較してですか？

Question

DFAに比べてNFAの利点：表現は少ないメモリを使用します。

NFAと比較してNFAの欠点：応答が遅くなります。

他にも利点や欠点はありますか？

Answer 1

私は頭の上の主なトレードオフを釘付けにしたと思います。 NFAは、O（n）空間でO（2 ⁿ）の異なる構成をエンコードできるため、同じ言語のDFAが指数関数的なスペースを取る可能性があるため、メモリ効率が高くなります。同様に、NFAsのアップデートが遅くなることは間違いありません。 NFAsをシミュレートするためのほとんどのアルゴリズムは、DFAsの状態遷移（nは状態数）とO（1）時間を計算するためにO（n）時間かかる。

2つの点にはいくつか違いがあります。まず最初に、DFAはエンコードする方が簡単です。なぜなら、状態とシンボルの各ペアについて、正確に1つの遷移があるからです。これは自然に、遷移表の多次元配列に適しています。対照的に、NFA（またはより悪いのは、ε-NFA）は、通常、任意の状態に対して多数の遷移が存在する可能性があるため、より複雑な表現を必要とする。しかし、NFAsには、複雑な構造からオートマトンへの多くの変換がNFAsの方が簡単であるという利点があります。例えば、正規表現から一致するオートマトンの正式な構成は、変換がより小さいε-NFAを再帰的に構築し、次いでそれらをε-movesを用いて一緒に結合することによって最もよく表現されるので、DFAよりもむしろε-NFAを生成する。正規表現をDFAに直接変換することは可能ですが、それを行うことはかなり困難です。同様に、LR（k）パーサーを生成するための多くのアルゴリズムは、ハンドル認識オートマトンがDFAの代わりにNFAに関してどのように機能するかを探ることにより、より直観的に動機づけることができます（ただし、これらのパーサーを生成するほとんどのアルゴリズムはNFAではなくDFA ）。

希望すると便利です。

Answer 2

NFA表現はよりコンパクトですが、DFAのシミュレーションは簡単です。 NFAをDFAに縮小すると指数関数的にサイズが大きくなることがあります