47

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

4

5 に答える 5

79

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

有限オートマトンは、状態を持ち、入力を読み取るプロセッサであり、各入力文字は潜在的に別の状態に設定します。たとえば、状態は「2つのCを続けて読み取る」または「単語を開始する」の場合があります。これらは通常、テキストをすばやくスキャンしてパターンを見つけるために使用されます。たとえば、ソースコードを字句スキャンしてトークンに変換する場合などです。

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

これで、「数値または識別子の読み取り」を状態自体として表現できるようになり、突然NFAが不要になりました。NFA内の状態の組み合わせを状態自体として表現すると、NFAよりもはるかに多くの状態を持つDFAが得られますが、これは同じことを行います。

どちらが読みやすく、書きやすく、扱いやすいかという問題です。DFA自体は理解しやすいですが、NFAは一般的に小さいです。

于 2010-10-20T15:40:13.147 に答える
17

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]

于 2011-01-26T20:19:35.310 に答える
7

ジェフリー・フリードルの著書 『 Mastering Regular Expressions』から言い換えた、単純で非技術的な説明。

警告：

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

編集：フリードルと私は確かに間違っているようです。以下のイーモンの素晴らしいコメントをチェックしてください。

元の答え：

DFAエンジンは、入力文字列を1文字ずつステップスルーし、この時点で正規表現が一致する可能性のあるすべての方法を試行（および記憶）します。文字列の最後に到達すると、成功を宣言します。

AAB文字列と正規表現を想像してみてくださいA*AB。次に、文字列を1文字ずつステップスルーします。

  1. A：

    • 最初のブランチ：。で一致させることができますA*。
    • A*2番目のブランチ:(ゼロの繰り返しが許可されます）を無視しA、正規表現で2番目のブランチを使用することで一致させることができます。

  2. A：

    • 最初のブランチ：を展開することで一致させることができますA*。
    • 2番目のブランチ：と一致することはできませんB。2番目のブランチは失敗します。だが：
    • A*3番目のブランチ：展開せず、代わりに2番目のブランチを使用することで一致させることができますA。

  3. B：

    • A*最初のブランチ：正規表現内で展開したり、次のトークンに移動したりしても、一致させることはできませんA。最初のブランチは失敗します。
    • 3番目のブランチ：一致させることができます。やったー！

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

NFAエンジンは、トークンごとに正規表現トークンをステップスルーし、文字列で可能なすべての順列を試行し、必要に応じてバックトラックします。正規表現の終わりに達すると、成功を宣言します。

以前と同じ文字列と同じ正規表現を想像してみてください。次に、トークンごとに正規表現トークンをステップスルーします。

  1. A*：一致しAAます。バックトラック位置0（文字列の先頭）と1を覚えておいてください。
  2. A：一致しません。しかし、戻って再試行できるバックトラックポジションがあります。正規表現エンジンは1文字後退します。今A一致します。
  3. B：一致します。正規表現の終わりに達しました（1つのバックトラック位置に余裕があります）。やったー！
于 2010-10-20T15:05:09.747 に答える
4
于 2016-10-22T23:44:32.783 に答える
0

通常の表現、 JanGoyvaertsによる完全なチュートリアルで与えられた説明が最も使いやすいと思います。このPDFの7ページを参照してください。

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

7ページで述べた他のポイントの中には、テキスト指向エンジンと正規表現エンジンの2種類の正規表現エンジンがあります。ジェフリー・フリードルはそれらをそれぞれDFAエンジンとNFAエンジンと呼んでいます。 ...遅延数量詞や後方参照などの特定の非常に便利な機能は、正規表現指向のエンジンでのみ実装できます。

于 2016-04-26T20:43:24.040 に答える