問題タブ [dfa]

2 つの任意の正規表現が等しいかどうかを調べる方法はありますか? 私には複雑な問題のように見えますが、DFA の単純化メカニズムか何かがあるのではないでしょうか?

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

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

編集：

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

の特定のインスタンスによって文字列の最初の文字として一致する可能性のあるすべての文字のセットを計算できるようにしたいと考えていますjava.util.regex.Pattern。より正式には、特定の正規表現に相当する DFA を考えると、開始状態からのすべての出力遷移のセットが必要です。

例：

セットfirstには次の要素が含まれている必要があります。

何か案は？私は自分で DFA を構築し、関連する状態をそのように決定できることをよく知っていますが、そのような面倒なことは避けたいと思います (読んでください: それは私にとってそれほど価値がありません)。私のホスト言語は実際には Scala であるため、すべてのコア Scala ライブラリにアクセスできることに注意してください (それだけの価値があります)。

正規表現を表す特定の DFA があります。入力ストリームに対して DFA を照合し、最小最長一致だけでなく、可能なすべての一致を取得したいと考えています。

例えば：

正規表現: a*ba|baa

入力: ああああああああああああああ

結果：

1. あああああ
2. あば
3. バ
4. ばあ

典型的なコンパイラコースを構成するオンラインコース/大学の講義を知っている人はいますか? 私はコンピューティングの理論を持っていましたが、残念ながら私の学校ではコンパイラ構築のコースを提供していませんでした。

そこに講義があることは知っています。特に優れた製品の推奨事項を期待していました。

また、この分野の初心者向けの本はありますか? 少なくともドラゴンブック以外の何か。初級者レベルは問題ありません。市場には中級者向けのテキストがたくさんあることは知っています。

ありがとう！

私はこの入力ファイルを持っています:

最初の行は、テスト ケースの数を表します。

各テスト ケースは 3 つの整数で始まります。最初はオートマトンの状態数、次はアルファベットのシンボル数、そして最終状態数です。

次の行はアルファベットです。シンボルが一緒に表示されます。

次に、遷移関数を記述する状態の数に等しい数の行があります。この行グループの最初の行は、オートマトン (qo) の最初の状態の遷移関数を表し、最初の要素は、アルファベットの最初の記号がこの状態に移行したときに到達する状態を表します。元の問題文からこれを理解するのに苦労しました。これは私がそれを見るようになった最も簡単な方法です：

台詞：

同等：

次に、オートマトンの最終状態を示す行があります。

次に、初期状態と入力文字列の数を示す行が表示されます。

次に、入力文字列を含む行が来ます。

このプログラムの出力は次のようになります。

文字列が受け入れられるか拒否されるか、およびどの状態で終了したかを示す必要があります。

これまでのところ、入力を使用して作業をコーディングしただけです。

オートマトンを表現するのに最も便利な方法がわかりません。Graph クラスを作成する必要がありますか? 単純に配列を使用する必要がありますか? 配列にどのようなロジックを適用しますか?

編集これは、マイケル・ボルグワードのアドバイスに従って私が作成したコードです。トランジションは機能しますが、処理中に文字列が状態 0 で停止する理由がわかりません。 **

正規表現を DFA にコンパイルし、DFA を照合しながらグループ キャプチャを実行できる、Java 用の (無料の) 正規表現エンジンはありますか?

どちらも DFA にコンパイルされる dk.brics.automaton と jrexx を見つけましたが、どちらもグループ キャプチャを実行できないようです。私が見つけた他のエンジンはNFAにコンパイルされるようです。

問題:文字列の大きな静的リストが提供されます。データとワイルドカード要素 (* と ?) で構成されるパターン文字列。アイデアは、パターンに一致するすべての文字列を返すことです - とても簡単です。

現在の解決策:私は現在、大きなリストをスキャンし、各エントリをパターンに対してグロビングする線形アプローチを使用しています。

私の質問:検索の複雑さが O(n) 未満になるように、大きなリストを格納できる適切なデータ構造はありますか?

おそらく接尾辞-trie に似たものですか？ハッシュテーブルでバイグラムとトリグラムを使用することも検討しましたが、返された単語のリストとパターンのマージに基づいて一致を評価するために必要なロジックは悪夢であり、さらにそれが正しいとは確信していませんアプローチ。

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

正規表現が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が続くすべての文字列のセット）...

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

交差法を使用して 2 つの dfa を結合するにはどうすればよいですか?