問題タブ [nfa]

これには何らかの証拠がありますか？現在の NFA が最小額であることをどのように知ることができますか?

おもちゃのNFA正規表現マッチャーを移植して、ちょっとしたclojureを学ぼうとしています。明らかに、私の主な問題はグラフの表現と操作です。私は実用的な解決策を見つけましたが、私の実装（gensym基本的にはポインターをエミュレートするために使用）は、私の口の中に不快な味を残します。

グラフの表現と一般的な読みやすさとイディオムの両方について、改善を提案するように気をつけてください。（元の命令型ソリューションは、現在のソリューションよりもはるかに読みやすくなっています）。

乾杯！

正規表現をNFAに変換するアルゴリズムがあることを知りました。

しかし、NFA を正規表現に変換するアルゴリズムがあるかどうか疑問に思っていました。あるとすれば、それは何ですか？

ない場合は、すべての NFA が正規表現に変換できるかどうかも疑問です。正規表現で表現できないNFAはありますか?

ありがとうございました！:D

試合は重複する可能性があります。

ただし、同じ位置から始まる複数の一致が見つかった場合は、短いものを選択してください。

たとえば、文字列"abcabdcd"で正規表現部分"a.*d"を見つけるには、答えは { "abcabd" , "abd" } になります。また、「abcabdcd」と「abdcd」は含めないでください。

レクサーに DFA ミニマイザーを実装しようとしていますが、式の最小 DFA であるとは思えない DFA を生成することはできません。

後置正規表現からトムソン構築を使用して構築された NFA から DFA を構築しています。ドラゴンブックに書かれていることとほぼ同じです。レクサーを作成するために、いくつかの NFA が開始状態からのイプシロン遷移を使用して結合されます。DFA アルゴリズムが適用されるのは、この結合された NFA です。

では、デッドステートの除去とステートの最小化のための優れたテストベッドとなる DFA を生成する「既知の」正規表現はありますか?

もちろん、奇妙な DFA をハックしてそれにアルゴリズムを適用することもできますが、それは実際には適切なテスト ケースではないでしょうか? 私が構築している DFA のメソッドがデッド ステートになりにくいようにするためである場合、その情報は同様に価値があります。その場合、ステート エリミネーション機能の実装を完全にスキップできるからです。

編集：正確に答えるために実装の詳細が必要な場合は、コードはgithub、特にNFA.csおよびDFA.csクラスで入手できます。さらに、私が使用している構築アルゴリズムに関する一連のブログ記事を書いています。

2つの非決定性有限オートマトンM1とM2が与えられた場合、 M1によって受け入れられた言語がM2によって受け入れられた言語のスーパーセットであるかどうかを判断するための効率的なアルゴリズムはありますか？

2 つの正規表現を取り込んで、それらが同型かどうか (つまり、まったく同じ文字列セットに一致するかどうか) を判断するライブラリが必要です。たとえば、a|b は [ab] と同型です。

私が理解しているように、正規表現はNFAに変換でき、場合によってはDFAに効率的に変換できます。次に、DFA を最小限の DFA に変換できます。これは、私が正しく理解している場合は一意であるため、これらの最小限の DFA を比較して同等性を確認できます。すべての正規表現 NFA を DFA に効率的に変換できるわけではないことを認識しています (特に、真に「正規」ではない Perl 正規表現から生成された場合)。ありえない。

これを行うことについてオンラインでたくさんの記事や学術論文を目にします (また、学生にこれを行うように依頼するクラスのプログラミング課題もいくつかあります) が、この機能を実装するライブラリを見つけることができないようです。私は Python や C/C++ ライブラリを好みますが、どの言語のライブラリでもかまいません。そのようなライブラリがあるかどうか誰かが知っていますか? そうでない場合、誰かが私が出発点として使用できる近くにあるライブラリを知っていますか?

この言語が規則的かどうかを証明するにはどうすればよいですか?

L = {a ⁿ b ⁿ : n≥1} 和集合 {a ⁿ b ⁿ⁺² : n≥1}

正規表現についても教える計算コースを受講しています。答えられない難しい質問があります。

最大で2組の連続する0を含む単語を受け入れる言語の正規表現を見つけます。アルファベットは0と1で構成されます。

最初に、その言語のNFAを作成しましたが、それをGNFAに変換できません（後で正規表現に変換されます）。この通常の表現をどのように見つけることができますか？GNFAに変換するかどうか？

プロッティング マシン用の軽量な C ライブラリはありますか? 検索を行いましたが、見つかったライブラリはすべてタスク固有ではなく、重いです。プロッティング マシン用の軽量ライブラリが必要です。