問題タブ [nfa]

コンパイラに関する質問があります。

{(ab)^n | n >= 0} は正規言語ですか?

しかし、私はその NFA を描くことができます。しかし、ポンピング補題を使用すると、矛盾した答えが得られます。

誰でも私を助けることができますか？

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

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

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

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

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

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

正規表現の非決定論的有限状態オートマトンへの変換について質問があります。

（a * | b *）*をNFAに変換します。私の試みは次のとおりです。

私は完全にマークから外れていますか？またはいくらかそこに？

NBE=>ε

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

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

(ab u aab u aba)*

私はそれをしましたが、その正しさについてのフィードバックが欲しいです:

正しければ: (ab u aab u aba)* をさらに単純化できますか?

そうでない場合: 何を見逃しましたか?

編集: 3 つの最終状態すべてから初期状態に戻る e トランジションが欠落しているようです。e トランジションで古い初期状態に移動する初期および最終の新しい状態が必要です。（クリーネスタールール）。

PS と を単純化することもできます(a u b)*aababか(a u b)*a(a u b)(a u b)(a u b)(a u b)。

単純化/最小化する方法がない場合、非常に長いDFAになるため、私が尋ねる理由...

明らかな選択は、すべての可能な入力を使い果たすことです。私はやったと思います。しかし、それが有効かどうかはよくわかりません。また、非決定性有限オートマトンの規則に違反していません。

私のNFAは次のように与えられます：(ab u aab u aba)*そして以下は私の図です。

私は何かを逃したことがありますか？

特定の正規表現の実装がDFAまたはNFAに基づいているかどうかという問題に直面しています。

これを理解するための出発点は何ですか。次のように尋ねることもできます。何を探していますか? 基本的なパターンおよび/または特性は何ですか? 適切で説明的なリンクまたは少しの比較 (正規表現に直接専念していなくても) はまったく問題ありません。

Java で NFA をシミュレートする割り当てが与えられました。NFAをシミュレートする必要がある次の正規表現は次のとおりです

電子シンボルが多すぎると思います。以下の画像が正しいかどうか疑問に思っていました。