finite-automata - DFAに対するNFAの長所/短所およびその逆

Question

相互に比較した場合、DFAとNFAの両方の相対的な長所と短所は何ですか？

DFAはNFAよりも実装が簡単であり、NFAはDFAよりも受け入れ状態に到達するのが遅いことを知っていますが、他に明確でよく知られている長所/短所はありますか？

Answer 1

NFAとDFAは、同じ言語セット（正規言語）を受け入れます。

NFAの直接実装（DFAはNFAのサブセットであるためDFAではない）は通常、バックトラックを許可する必要がありますが、DFAの直接実装は入力長と同じ数のステップしか必要としないため、その意味でDFAは「到着」します。答えで」同等のNFA（DFAではない）よりも高速です。

特定の言語またはREに対応するFAを（たとえば、アルゴリズムによって）見つけようとする場合、通常、最初にNFAに到達する方が簡単です（ルールがそれほど厳密ではないため）。NFAの存在はDFAの存在と同じくらい良いので、これはFAの存在を実証しようとするときに特に当てはまります。DFAが必要な場合は、（a）NFAを同等のDFAに変換し、（b）DFAを最小化するためのアルゴリズムが存在します。

大まかに一般化すると、DFAは高速ですが、より複雑になり（状態と遷移の数に関して）、NFAは低速ですが、より単純になります（同じ用語で）。

Answer 2

DFAに対するNFAの利点は、常に「正しいパスを選択する」という特性です。アルゴリズムでは「正しいパスを選択する」とは言えないため、通常はNFAからDFAへの変換が機能し、複数のNFA状態を象徴するDFA状態が作成されます。したがって、NFAが状態Aにあり、A、B、またはCに進むことを選択できる場合、DFAの次の状態は{A、B、C}になります。

これは、長所と短所を説明しています。DFAは、次の状態が関数によって決定されるため、簡単に実装できます。NFAは多くのパスから選択できるため、ユーザーは必要なものを簡単に表現できます。

Answer 3

DFAに対するNFAの明確な利点の1つは、NFAを使用して、2つ（またはそれ以上）の言語の和集合、共通部分、概念などの言語を表すFAを簡単に構築できることです。つまり、少し単純なFAが仕事の一部を実行している場合は、NFAを使用してそれらを簡単に組み合わせることができます。DFAを使用している間は、すべての作業を単独で実行する新しいオートマトンを構築する必要があります。

ほら、実装する方が簡単です。しかし、あなたが言ったように時間の問題があります。