問題タブ [nfa]

正規表現をNFAに変換するための優れたライブラリはありますか？私はこの主題に関する多くの学術論文を目にします。それらは役に立ちますが、コードの動作にはあまり影響しません。

私の質問は、部分的には好奇心によるものであり、部分的には、私が取り組んでいる本番システムでの正規表現マッチングを高速化する実際の必要性によるものです。学習のためにこの主題を探求するのは楽しいかもしれませんが、それがパターンマッチングを高速化するための「実用的な」解決策であるかどうかはわかりません。私たちはJavaショップですが、どの言語の優れたコードへのポインターも喜んで受け取ります。

編集：

興味深いことに、Javaの正規表現がすでにNFAであることを知りませんでした。この論文のタイトルは、私がそうではないと信じるように導きました。ちなみに、現在Postgresで正規表現のマッチングを行っています。単純な解決策がマッチングをJavaコードに移動することである場合、それは素晴らしいことです。

Python（任意のバージョン）が正規表現を評価するためにNFA（非決定性有限オートマトン）を使用したかどうか、または他のメカニズムを使用したかどうかを誰かが知っていますか？可能な場合は、リンク/参照を提供してください。

実数を決定する NFA はありますか?

これで私を助けてくれるといいのですが…。

正規表現がNFAおよび/またはDFAによって受け入れられるかどうかをどのように判断するかという主な質問があります。

たとえば。私の質問によると、正規表現のどれが同等ですか？説明...1。（a + b）** b（a + b）** b（a + b）*

2.a ba ba *

3.a ba b（a + b）*

NFAとDFAを描画してから、最小化アルゴリズムで見つける必要がありますか？そうすると、どの正規表現がNFA / DFAによって受け入れられるかをどのようにして知ることができるので、答えから始めることができますか？そのとても紛らわしい....

2つ目は非常によく似たもので、質問は言語（a ^ nb ^ n |n>1}がDFAによって受け入れられないことを示すように求めています...grrrrr...どうすればこれを知ることができますか？（ところでこれはいくつかのaの後に同じ数のbが続くすべての文字列のセット）...

はっきりと説明できたらいいのに…。

F# で記述されたオープン ソース ライブラリをお勧めできますか?FA の構築と基本的なアルゴリズム (NFA から DFA への変換、FA の最小化など) のジェネリック型を提供します。

私は現在、スキャナージェネレーターに取り組んでいます。ジェネレーターはすでに正常に動作しています。しかし、文字クラスを使用すると、アルゴリズムが非常に遅くなります。

スキャナー ジェネレーターは、UTF8 でエンコードされたファイル用のスキャナーを生成します。文字の全範囲 (0x000000 から 0x10ffff) をサポートする必要があります。

任意の演算子「.」などの大きな文字セットを使用する場合 または Unicode プロパティ {L}、nfa (および dfa) には多くの状態 (> 10000) が含まれています。そのため、nfa から dfa への変換と最小の dfa の作成には長い時間がかかります (出力の最小の dfa に数個の状態しか含まれていない場合でも)。

これが、nfa の文字セット部分を作成する私の現在の実装です。

必要な状態のみを作成するために関数をより効率的に実装する方法を知っている人はいますか?

編集：

より具体的には、次のような関数が必要です。

文字 (int) を UTF8 エンコーディング byte[] に変換するヘルパー関数は、次のように定義されます。

上限は 2^n であり、これらが両方とも有限のマシンであることを考えると、n 状態 NFA と 2^n 以下の状態を持つ DFA の両方の交差が有効になるため、そう考えています。

私はここで間違っていますか？

NFA または DFA の遷移テーブルを記述するための標準構文はありますか?

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

おやすみなさい、

トランジションが .NET ディクショナリ構造に格納されている NFA/DFA を実装し、入力単語を受け取り、入力から何らかの方法で派生可能な一連の単語を認識するクラスがあるとします。さらに、オートマトンが、遷移文字のラベルを付け直すだけで、同じ長さの異なる単語に適用できる汎用テンプレートであるとします。実行時に入力単語の文字に従ってトランジションを再ラベル付けできるように、ディクショナリでトランジション関数をエンコードする最良の方法は何ですか?

どうもありがとうございました。