問題タブ [nfa]

私は NFA と DFA について学び始め、DFA の Berkley PDF の 1 つでこの質問をオンラインで見つけましたが、質問には解決策が添付されていませんでした。

{a, b}アルファベットを介して DFA M を入力として受け取り、L(M) = {a}それともL(M) =/= {a}?

ガイダンスをいただければ幸いです。

NFA を DFA に変換するコードを書いています。電源状態が {1,2,4} の場合、それを x などの一意の数値に変換する必要があります。また、x を取得するような逆マッピングを行う必要があります。電源状態を {1,2,4} として返す必要があります。

セット1,2,4の文字列表現のHashMapを持ち、値を一意の番号として持つことにしました。しかし、コードが大きくなるにつれて、(1,2,4) と (2,1,4) は両方とも同じセットですが、同じ文字列ではない可能性があります。次に、状態文字列をソートしてマップキーとして使用することを考えました。しかし、私のロジックは複雑なようです。

簡単なステートメントが与えられます:alphabet {0, 1}を受け入れるDFA を構築しますall the strings that end in 101。

私の質問は、それを設計するためのステップは何ですか? または、NFA を設計します。NFA を DFA に変換する明確な手順を知っているので、NFA を DFA に変換します。

注:- これは私にとってはマイナーなコースなので、正規表現や、おそらく DFA の構築に使用されるアルゴリズムなどを勉強したことはありません。

これまでのところ、正規表現は 1(0|1)*1|0(0|1)*0 です。0 または 1 自体が 1 桁であるため、終了状態としてカウントされるかどうか疑問に思っていますが、技術的には同じ数字で開始および終了しますか?

正規表現から NFA へのコンバーターを実装しようとしています。ほとんどのコードを記述しましたが、状態 (ノード) とエッジの表現を考慮して、サイクルを使用してグラフを作成する方法を見つけるのに苦労しています。

私のグラフ表現は次のとおりです。

正規表現を NFA に変換する私の関数は、基本的に正規表現のタイプのパターン マッチであり、正規表現のタイプと「最終状態」(NFA のすべての発信エッジが移動する場所) を取り込み、「開始状態」を返します。その正規表現の（部分的に構築された）NFAの。NFA フラグメントは、発信エッジ リストで構築された State を返すことによって構築されます。各エッジの終了状態は、再帰呼び出しによって構築されます。

ほとんどのコードは簡単ですが、グラフでサイクルを必要とする Kleene スターと + の NFA を構築するのに苦労しています。私の表現を考えると、次のような結果になります。

この時点で s が未定義であるため、明らかにこれはコンパイルされません。ただし、型チェッカーはそのような再帰的に定義された型を (正当に) 拒否するため、"rec" キーワードも追加できません。そしてまた...）。基本的に、ここには鶏が先か卵が先かという問題があります。完全に構築される前に、「状態」参照を別の状態に渡す必要があります。再帰呼び出しで。

参照/可変レコードを使用せずにこれを行う方法はありますか? これを可能な限り機能的に保ちたいのですが、状況を考えるとこれを回避する方法がわかりません...誰か提案がありますか?

AとBを受け入れるある種の文字列を受け入れるFAを設計することを楽しみにしています。

まず、A の数が B の 5 倍多い弦。

つまり L={w∈{A,B}* and (nA(W)-nB(W) mod 5=0)

また、文字列内の異なる数の文字を受け入れる FA:

いくつかの FA を設計しましたが、この複雑な弦では完全に機能しませんでした。

これをどのように設計すればよいですか？