問題タブ [dfa]

特定の言語のDFAはすべてのDFAのサブセットであるため、DFAはカウント可能であることに気付きました。DFAが特定の言語を受け入れる数が無限であることを証明する方法を知りたいですか？

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

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

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

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

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

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

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

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

正規言語の概念に少し混乱しています。すべての正規言語はdfaで受け入れることができ、dfaには常にループが含まれているためです。したがって、dfaは無限の数の文字列を受け入れることができるようです。それはすべての正規言語が無限であることを意味しますか？空集合はどうですか。正規言語ですか？

1. 言語が規則的でないことを示します。L = {a^nb^m : n>m}

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

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

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

Python で DFA を最小化するアルゴリズムを見つけようとしています。私はいくつかの例を見つけましたが、それらはすべてコードにクラスがあります。現在、.txt ファイルに配置されている DFA の定義を転送してそれらのクラスに配置する方法がわかりません。.txt は次の方法でフォーマットされます。

1. 行: コンマで区切られた一連の州を辞書順に並べたもの
2. 行: コンマで区切られた一連のアルファベット記号を辞書順に並べたもの
3. 行: コンマで区切られた許容可能な状態のセットで、辞書順に並べられています
4. 行: 最初の状態
5. その他のすべての行: 現在の状態、アルファベット記号->次の状態の形式の伝達関数

定義の例:

クラスの例

.txtファイルをロードします

が与えられ{a^(n+m) | n>= 2m}たとき、それが規則的か、文脈自由か、文脈自由でないかを述べ、DFA、CFG などを使用して証明します。

私の答え: n>=2m を表現する方法がないため、コンテキスト フリーではありません。大なり記号があいまいです。

私の答えが正しいかどうか疑問に思っています。

DFA ベースの正規表現マッチャー内で「単語境界」マッチを実装したいと考えています。誰かがこれがどのように行われるか教えてもらえますか?

背景を説明すると、現在「dk.brics.automaton」ライブラリを使用していますが、アサーション (\b単語境界など) をサポートしていません。私の主な目標は実際に正規表現の同等性を判断することであり、実際のマッチングを行うことではないため、DFA ベースのエンジンを使用する必要があります。

さらに、次の質問に対する回答は、これが可能であることを示しているようです: DFA ベースの正規表現マッチング - すべての一致を取得する方法は? 言うことによって

「ここでも、特別な命令を含むイプシロン遷移をシミュレーターに追加することでこれを管理します。アサーションがパスした場合、状態ポインターは続行されます。それ以外の場合は破棄されます。」

しかし、これが何を意味するのか、私にはよくわかりません。エンドポイントを見て、そのエンドポイントがアサーションを満たす場合にのみトラバースできる特別なタイプのイプシロン遷移でのみ実行できることを示唆していますか、または何らかの方法で構成された「通常の」イプシロン遷移で実行できますか? これらの「特別な」タイプのイプシロン遷移が必要な場合、これらをどのように決定できますか (つまり、標準の DFA に変換できますか)?

これを実際に実装する方法の説明へのポインタは大歓迎です。