問題タブ [dfa]

誰かがC＃でのNFAとDFAの優れた実装を知っていますか？おそらく両方の間の変換も実装していますか？私が望んでいるのは、NFAを構築し、それを自動的にDFAに変換できるようにすることですが、非常に長い時間がかかる独自のコードを作成する必要はありません。おそらく私が使用してIronPythonを使用してC＃と統合できるこのPythonコードがありますが、Pythonは遅いです。

正規表現用のステート マシン ジェネレーターを設計するのは簡単ではないことはわかっていますが、単純な文字列についてはどうでしょう (単純な文字列と言うときは、"abcd" のようなもの、つまり正規表現の構文がないものを意味します)。ステート マシンを使用して単純な文字列マッチャーを作成することを考えていましたが、実行時にステート マシンを生成したかったのです。

ステート マシン ジェネレーターへの入力は照合する文字列で、出力はステート マシンです。コードを探しているのではなく、これを行うためのメソッド/アルゴリズムを探しています。

はい、すぐに利用できるライブラリを使用できますが、そうではありません。

非決定性有限オートマトンを決定性有限オートマトンに変換できる Java ライブラリを探しています。ありますか？

与えられた 2 つの DFA の結合を構築するためのアルゴリズムの簡単な説明を誰かが持っていますか? たとえば、{0,1} に 2 つの DFA があるとします。

ユニオンを次のように示す結果の遷移テーブルがあります。

講義ノートに解決策の図を載せていますが、他の人がそれをどのように説明するかを知りたいです。このことから、状態値を使用してこれら 2 つの元のテーブルを本質的に「乗算」して、より大きな遷移テーブルを作成していることがわかります。したがって、結果のテーブルから DFA を引き出すことができます。これは正しく聞こえますか?また、すべての DFA ケースで機能するはずですか?それとも何か不足していますか?

NFA から DFA への変換アルゴリズムを SO コミュニティに簡潔に説明するよりもはるかに優れた人がいるでしょうか? (できれば 500 語以内で。) 私はかつて知っていたと思っていたことを混乱させるだけの図や講義を見てきました。状態図から最初の NFA 遷移テーブルを生成することにはほぼ自信がありますが、その後、イプシロンとサブセットで DFA を失います。

1) 遷移 (デルタ) テーブルで、新しい DFA 状態を表す列はどれですか? 生成された状態の最初の列ですか?

2) 以下の例の列 0 の行 {2,3} で、状態図に関して NFA について {2,3} は何を意味しますか? (申し訳ありませんが、写真で考えなければなりません。) そして、DFA で「入力 0 のループバック」になると思いますか?

3) テーブルから DFA への取得、または結果の DFA の受け入れ状態の認識に関する簡単な「経験則」はありますか?

有限自律

編集：これはドット形式の上記の表です。Regexidentを乾杯します。

そして、ここでレンダリングされた形式で：

注:この表には、状態の受け入れに関する情報が欠けているため、グラフにも含まれています。

Dragon Book で説明されている正規表現から DFA への直接変換アルゴリズムに基づいて、正規表現ベースの字句解析ジェネレーターを作成しています。

nullable、firstpos、lastpos、およびfollowpos連結ノード、交互ノード、およびクリーネスター ノードの関数を計算します。+(1 回以上) および?(0 回または 1回)の数量詞を追加したい。

nullable、firstpos、lastposは簡単に計算できますが、 についてはよくわかりませんfollowpos。これらの量指定子を構文解析段階の一部として実装せず、代わりに字句解析段階で書き直す方がよいでしょうか (これは kleene-star とオルタネーションに対する「構文糖衣」にすぎないと思います)。

私は、コンパイラでnfaまたはdfaを使用する方が適切であり、どのような状況であるかについての議論を探しています。nfaとdfaをシミュレートすることの時間計算量のトレードオフは何ですか？また、コンパイラーのどのような状況でどちらがより適切ですか？

まともな正規表現エンジンを探し始めました。このページ Benchmark of Regex Libraries にたどり着きました。RE2を使用することに決めたのは、このリストで最高の FSA エンジンと思われるからです。

私の最終的なアプリケーションは、C# で WPF を使用して構築されます。正規表現ライブラリは、バッチ モードでより多く使用されます。ただし、他のビジネス ロジックのほとんどは C# で記述されるため、C# を使用して RE2 ライブラリを使用する予定です。

誰かが同様のことをしたか、C# を介して RE2 を使用しただけで、アドバイスや指針がある場合は、それについて教えてください。

ありがとう。

アルファベット { a } を持つ言語Lの定義は、次のように与えられます。

L = {a ^nk | k > 0; n は正の整数定数です }

Lを認識するために DFA で必要な状態の数は?

私の意見では、k + 1 にする必要がありますが、よくわかりません。

ここに宿題の問題があります：

私は L が非正規であることを知っており、Kleene Star がクローズド オペレーションであることを知っているので、L_4 は非正規であると仮定します。

しかし、私の教授は上記の例を提供しました。彼は、が互いに等しいL = {0^p | p is prime}ことを証明することにより規則的であると述べました(この場合、 e は空の単語を意味します)。L*L(000* + e)

したがって、彼の方法には の正規表現を形成することが含まれていまし0^pたが、本質的に既に正規表現を持っている場合、どうすればそれを行うことができるでしょうか?