排他的または2つの決定論的有限オートマトン(決定論的な有限状態マシン)を作成する
-
28-09-2019 - |
質問
セットDFA 1:l1 = {q1、e、d1、s1、f} dfa 2:l2 = {q2、 e、d2、s2、f}
Qは状態のリストです。 ex 1、2、3、4またはa、b、c、d
Eは言語Exです。 0、1
Dは遷移セットExです。 {(a、0、b)}状態aはa 0でbになります
Sは開始状態です
Fは最終状態です
2つのDFAS L1とL2をどのように摂取し、排他的にしますか
解決 2
Q = Q1 X Q2;
e = e;
Dは、両方のシステムから一致するすべての遷移です。
S = S1交差S2;
F = F1 XOR F2
他のヒント
これがあなたを始めるためのいくつかの幅広いヒントを紹介します...
おそらく、状態Q3がQ1とQ2のデカルト産物の要素で識別される別のDFAを構築したいと思うでしょう。 S1とS2から、Q3のどの要素を開始状態として指定するかはかなり明白であるはずです。
次に、Q3のノード(Q1のN1、Q2のN2)を考えると、各入力に対してエッジがどこに行く必要があるかを簡単に把握するのは非常に簡単です。 F3は一連の状態(N1、N2)があり、ここで(F1 XOR N2のN1)が保持されます。
所属していません StackOverflow