DFA対NFAエンジン：能力と制限の違いは何ですか？

https://stackoverflow.com/questions/3978438

09-10-2019
|

質問

私は探しています 非技術的な 能力と制限に基づいて、DFA対NFAエンジンの違いの説明。

解決

決定論的な有限オートマトン（DFA）および非決定論的有限オートマトン（NFA）には、まったく同じ機能と制限があります。唯一の違いは、表記の利便性です。

有限のオートマトンは、入力を状態にして読み取るプロセッサであり、各入力文字が潜在的に別の状態に設定されます。たとえば、状態は「2つのCSを連続して読むだけ」または「ワードを開始する」かもしれません。これらは通常、テキストの迅速なスキャンに使用され、ソースコードの語彙スキャンなどのパターンを見つけてトークンに変換します。

決定論的な有限オートマトンは、一度に1つの状態にあり、実装可能です。非決定的有限のオートマトンは、一度に複数の状態になる可能性があります。たとえば、識別子が数字で始まる言語で、「数字を読む」状態があり、別の状態が「識別子を読む」と、 NFAは、「123」から始まる何かを読むと同時に両方になる可能性があります。実際に適用される状態は、単語の終わりの前に数値ではない何かに遭遇したかどうかによって異なります。

今、私たちは「数字または識別子を読む」を状態自体として表現することができ、突然NFAは必要ありません。 NFAの状態の組み合わせを州自体として表現すれば、NFAよりもはるかに多くの状態を持つDFAを持っていますが、同じことをします。

それは、読み書きが簡単な問題です。 DFAはそれ自体を理解しやすいですが、NFAは一般的に小さくなります。

他のヒント

これがMicrosoftからの非技術的な答えです：

DFAエンジンは、バックトラッキングを必要としないため、線形時間で実行されます（したがって、同じ文字を2回テストすることはありません）。また、可能な限り長い文字列を一致させることも保証できます。ただし、DFAエンジンには有限状態のみが含まれているため、パターンを背景と一致させることはできず、明示的な拡張を構築しないため、サブ発現をキャプチャできません。

従来のNFAエンジンは、いわゆる「貪欲な」マッチバックトラッキングアルゴリズムを実行し、特定の順序で正規表現のすべての可能な拡張をテストし、最初の試合を受け入れます。従来のNFAは、一致を成功させるために正規表現の特定の拡張を構築するため、サブエグポンッションマッチと一致する背景をキャプチャできます。ただし、従来のNFAバックトラックであるため、状態が異なる経路に到達した場合、まったく同じ状態を複数回訪れることができます。その結果、最悪の場合はゆっくりとゆっくりと実行できます。従来のNFAは見つけた最初の試合を受け入れるため、発見されていない他の（おそらくより長い）一致を残すこともできます。

POSIX NFAエンジンは、従来のNFAエンジンのようなものですが、可能な限り長い一致が見つかったことを保証することができるまでバックトラックを続けています。その結果、POSIX NFAエンジンは従来のNFAエンジンよりも遅く、POSIX NFAを使用する場合、バックトラッキング検索の順序を変更することで、より長いマッチよりも短いマッチを好むことはできません。

従来のNFAエンジンは、DFAまたはPOSIX NFAエンジンよりも表現力があるため、プログラマーに好まれています。最悪の場合はゆっくりと実行できますが、あいまいさを減らしてバックトラッキングを制限するパターンを使用して、線形または多項式時間の一致を見つけるように操縦することができます。

http://msdn.microsoft.com/en-us/library/0yzc2yb0.aspx

ジェフリー・フリードルの本から言い換えられた、シンプルで非技術的な説明正規表現のマスター.

警告:

この本は一般に「Regex Bible」と見なされていますが、DFAとNFAの間で行われた区別が実際に正しいかどうかについては、いくつかの論争があるように見えます。私はコンピューターの科学者ではありません。また、「定期的な」表現であるものの背後にある理論のほとんどがわかりません。論争が始まった後、私はこのためにこの答えを削除しましたが、それ以来、他の答えへのコメントで言及されています。私はこれについてさらに議論することに非常に興味があります - それはフリードルが本当に間違っているということでしょうか？それとも、フリードルが間違っていました（しかし、昨日の夕方、その章を読み直しましたが、それは私が覚えていたようです...）？

編集： フリードルと私は本当に間違っているようです。以下のEamonの素晴らしいコメントをご覧ください。

元の答え：

a DFAエンジン ステップスルー 入力文字列 キャラクターによるキャラクターと試み（および覚えている）この時点で、正規表現が一致する可能性のあるすべての方法。文字列の終わりに達した場合、成功を宣言します。

文字列を想像してみてください AAB そして正規表現 A*AB. 。今、私たちは文字で文字で踏み込みます。

A:
- 最初のブランチ：一致させることができます A*.
- 2番目のブランチ：無視して一致させることができます A* （ゼロの繰り返しが許可されています）2番目の使用 A 正規表現で。
A:
- 最初のブランチ：拡大することで一致させることができます A*.
- 2番目のブランチ：一致することはできません B. 。 2番目のブランチは失敗します。だが：
- 3番目のブランチ：拡張しないことで一致させることができます A* 2番目を使用します A 代わりは。
B:
- 最初のブランチ：拡大しては一致できません A* または、正規表現で次のトークンに移動することによって A. 。最初のブランチは失敗します。
- 3番目のブランチ：一致させることができます。 hooray！

DFAエンジンは、文字列にバックトラックすることはありません。

an NFAエンジン ステップスルー 正規表現 トークンによるトークンは、必要に応じてバックトラッキングをして、ひもにすべての順列を試みます。正規表現の終わりに達した場合、成功を宣言します。

以前と同じ文字列と同じ正規表現を想像してください。トークンによる正規表現トークンを踏み出しました：

A*: ：マッチ AA. 。バックトラッキング位置0（文字列の開始）と1を覚えておいてください。
A: ：一致しません。しかし、戻ることができるバックトラッキングポジションがあり、再試行できます。 Regexエンジンは1つの文字をバックバックします。今 A マッチ。
B: ：マッチ。正規表現の終わりに達しました（1つのバックトラッキング位置が余裕があります）。 hooray！

NFAとDFAはどちらも有限のオートマトンです。

どちらも、開始状態、成功（または「受け入れる」）状態（または成功状態のセット）、および遷移をリストする状態のテーブルとして表すことができます。

DFAの状態テーブルでは、それぞれ <state₀, input> キーは1つだけにトランジットします state₁.

NFAの状態テーブルでは、それぞれ <state₀, input> aに通過します セットする 州の。

DFAを採取するときは、入力記号のシーケンスである開始状態にリセットし、それがどのような終了状態にあるか、そしてそれが成功状態であるかどうかを正確に知っています。

ただし、NFAを服用すると、各入力記号に対して、可能な結果状態のセットを調べ、（理論的には）無作為に、非決定論的に、それらのいずれかを選択します。その入力文字列の成功状態の1つにつながる一連のランダム選択が存在する場合、DFAはその文字列で成功すると言われます。言い換えれば、あなたはそれが魔法のように常に正しいものを選択するふりをすることが期待されています。

コンピューティングの初期の質問の1つは、NFAがその魔法のためにDFAよりも強力であるかどうかであり、答えは いいえ NFAは同等のDFAに翻訳できるためです。 それらの能力と制限は、互いにまったくまったく同じです。

説明が与えられていると思います 正規表現、完全なチュートリアル Jan Goyvaertsが最も使いやすい。このPDFの7ページを参照してください：

https://www.princeton.edu/~mlovett/reference/Regual-Expressions.pdf

7ページで作成された他のポイントの中で、正規表現エンジンには、テキスト指向エンジンとregex指向エンジンの2種類があります。ジェフリー・フリードルは、それぞれDFAエンジンとNFAエンジンを呼び出します。 ...怠zyな数量詞や背景などの特定の非常に有用な機能は、regex指向のエンジンでのみ実装できます。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow