問題タブ [nfa]

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

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

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

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

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

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

有限自律

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

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

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

私の字句解析ジェネレーターでは、NFA の構築に McNaughton と Yamada のアルゴリズムを使用し、I から J に遷移するそのプロパティの 1 つは、J の位置に char でマークされています。

したがって、NFA の各ノードは、次の可能な状態のリストとして単純に表すことができます。

このタイプのデータを格納するのに最適なデータ構造はどれですか? 可能なすべての状態をすばやく検索し、使用するスペースを少なくする必要がありますが、挿入時間はそれほど重要ではありません。

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

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

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

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

ありがとう。

トランスデューサーとNFAの違いを教えてもらえますか？

DFA に対する NFA の利点: 表現はより少ないメモリを使用します。

NFA と比較した NFA の欠点: 答えに到達するのが遅い。

他にメリットやデメリットはありますか？

私は正規表現を与えられました、そして私はそれをNFAそしてDFAに隠蔽することになっています。正規表現は次のとおりです。

a（b | c）* a | aac * b

次に、トムソンのアルゴリズムを使用してこれをNFAにカバーしました。

これがDFAです。

誰かが私が間違っているか正しいかを私に知らせてください。

誰かがこの質問で私を助けてくれますか?

NFA を言語が L(A) の補語である DFA に変換するアルゴリズムを説明してください。補数は、A のアルファベットに関して取得する必要があります。構造が機能する理由についての非公式な議論が与えられます。正式な証明をする必要はありません。

どんな種類のガイダンスも大歓迎です...