特定のregex implementationがDFAまたはNFAに基づいているかどうか、私は疑問に直面しています。正規表現の実装でDFAまたはNFAが使用されているかどうかを調べるにはどうすればよいですか？
私がこれを理解するための出発点は何ですか？ 1つはまた質問することができる：何を私は探している？基本的なパターンや特性は何ですか？良い説明リンクや少しの比較（たとえ直接正規表現に専念していなくても）はまったく問題ありません。
私はあなたがアルゴリズムではなく（正規の意味で） "正規表現の実装"を意味すると思います。
あなたは一つの方法または他の問題を引き起こすことが知られている既知の表現でテストすることができます。また、どちらかで実装するのが容易な機能を探している（これは信頼できる方法ではない - 正規表現エンジンの開発者は、以前は難しいものを実装する新しい方法を見つける）。
は通常の答えは、ドキュメントを読んで、または既知の基準（ "Mastering Regular Expressions"文書多くの一般例）で見ることです。最後に、なぜ著者に尋ねないのですか？それはブラックボックスだ場合私はこの回答を受け入れるでしょう、なぜなら、著者に尋ねる明白な提案のためです。私はそれについても考えていなかった:)ピート・カークハムの答えは非常に貴重でもある。 – Jan
、それにいくつかの入力を与え、グラフin this discussion of NFS vs backtracking regex implementationsを参照して、病的な場合に、その時間特性を測定します。 （NFSグラフは秒ではなくマイクロ秒であることに注意してください）。
また、純粋なNFAの場合、バックトラックを必要とするいくつかの「正規表現」パーサーがある非正規の機能はありません。
また、RxParserクラスのドキュメントを参照してください。ドキュメンテーションはWeb上で利用できないように見え、ブラウズするにはスクイークランタイムが必要です。
http://cstheory.stackexchange.com/に投稿することを検討してください。 –
私はあなたの用語が少し後方にあると思います。 NFAsには複数の実行パスが存在する可能性があるため、バックトラックを必要とします。バックトラックはDFAをうまくやってくれません。とにかく一方通行しかできないからです。 – phs
http://lambda.uta.edu/cse5317/notes/node9.htmlもあなたの興味に関連しているかもしれません。通常のNFAを評価するには、アルゴリズムが一連の状態（バックトラック）を保持する必要があります。ここでDFAエバリュエーターは常に正確に1つのオートマトン状態を保持します。 – phs