問題タブ [dfa]

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

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

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

これがDFAです。

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

CS クラスの McNaughton-Yamada アルゴリズムを使用して DFA を構築する必要があります。問題は、アルゴリズムが補足資料であり、それが正確に何であるかがはっきりしないことです. 正規表現を指定してDFAを見つける方法ですか、それともDFAを見つけて最小化していますか? この件に関する情報が見つからないようです。

クラスで DFA を見つけた後にインストラクターが示した最小化ルーチンは、私たちの本で説明されている「マーク」最小化と何ら変わらないように見えるので、私は混乱しています。

お返事をありがとうございます、

ネイサン

決定論的有限オートマトンをプッシュ ダウン オートマトンに変換するアルゴリズムを探しています。

どんな助けでも感謝します。

ありがとう！

DFAには、次の4つのプロパティが必要です。

• DFAにはN個のノードがあります

• 各ノードには2つの発信遷移があります。

• 各ノードは、他のすべてのノードから到達可能です。

• DFAは、あらゆる可能性から完全に均一なランダム性で選択されます

これは私がこれまでに持っているものです：

1. N個のノードのコレクションから始めます。
2. まだ選択されていないノードを選択します。
3. その出力を他の2つのランダムに選択されたノードに接続します
4. 一方の遷移1ともう一方の遷移0にラベルを付けます。
5. すべてのノードが選択されていない限り、2に進みます。
6. 着信接続のないノードがあるかどうかを確認します。
7. その場合、複数の着信接続があるノードから着信接続を盗みます。
8. 着信接続のないノードがない場合を除いて、6に進みます

ただし、これはアルゴリズムが正しくありません。ノード1の2つの接続がノード2（およびその逆）に接続され、ノード3の2つの接続がノード4（およびその逆）に接続されているグラフを考えてみます。それは次のようなものです：

1 <==> 2

3 <==> 4

ここで、<==>とは、双方向の2つの発信接続を意味します（つまり、合計4つの接続）。これは2つのクリークを形成しているように見えます。つまり、すべての州が他のすべての州から到達できるわけではありません。

誰かがアルゴリズムを完了する方法を知っていますか？または、誰かが別のアルゴリズムを知っていますか？二分木を使ってこれを構築できることを漠然と思い出しているようですが、それについてはよくわかりません。

C/C++/Java で DFA をリンク リストとして実装する方法を知りたいです。

グラマー ファイルから antlr を使用してレクサーを生成すると、一連の文字列が 16 進形式で生成されることに気付きました。

これらの文字列は、次のトークンを予測するために DFA によって使用されます。

これらの文字列は何を意味し、どのように生成されますか。

私が参照している文字列は、生成されたレクサーに次のように表示されます (コンストラクターで DFA に渡されます)。

編集：

私たちを始めるために、私は自分の質問で答え始めます

acceptS[i] = 可能なトークンの識別子を含む配列 (多くの -1 値が含まれている理由はわかりません)

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

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

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

nfaをdfaに変換するプログラムを作成したいのですが、ユーザーがグラフを描画してから、プログラムでdfaに変換します。どうすればいいですか？

DFA を最小化するために Brzozowski のアルゴリズムを実装しようとしています。以下は同じアルゴリズムです。

ここでr()は NFA の反転であり、D()NFA を DFA に変換します。

r()しかし、Googleで検索してもあまり情報が得られないという意味がわかりません。

誰でもr()NFAとは何か説明してもらえますか?

利用可能な他の単純なアルゴリズムまたは C++ 実装があれば、リンクを教えてください。

相互に比較した場合、DFAとNFAの両方の相対的な長所と短所は何ですか？

DFAはNFAよりも実装が簡単であり、NFAはDFAよりも受け入れ状態に到達するのが遅いことを知っていますが、他に明確でよく知られている長所/短所はありますか？