math - 2つの決定性有限オートマトン（決定性有限状態マシン）からの排他的論理和の作成

Question

2つのDFA（決定性有限オートマトンまたは決定性有限状態マシン-これ以降はDFAと呼びます）セットで定義DFA 1：L1 = {Q1、E、D1、s1、F} DFA 2：L2 = {Q2、 E、D2、s2、F}

Qは状態のリストです。例1、2、3、4またはa、b、c、d

Eは言語例です。0、1

DはトランジションセットExです。{（a、0、b）}状態aは0でbになります

sは開始状態です

Fは最終状態です

どのように、排他的に、または2つのDFAL1とL2を使用しますか

Answer 1

ここにあなたが始めるためのいくつかの広いヒントがあります...

おそらく、状態Q3がQ1とQ2のデカルト積の要素で識別される別のDFAを構築することをお勧めします。s1とs2から、Q3のどの要素を開始状態として指定する必要があるかはかなり明白です。
次に、Q3の任意のノード（Q1のn1、Q2のn2）が与えられると、各入力のエッジがどこに行く必要があるかを理解するのは非常に簡単です。そして、F3は（F1のn1 XOR F2のn2）が成り立つ状態のセット（n1、n2）になります。

Answer 2

Q = Q1 X Q2;

E = E;

Dは、両方のシステムから一致するすべての遷移です。

s=S1はS2と交差します。

F = F1 XOR F2