Erstellen eines Exklusiv Oder aus zwei deterministischen endlichen Automaten (deterministischen Finite-State Machines)

Question

Zwei DFAs (deterministische endliche Automaten oder deterministischer Fininte-State Machines - Welche DFAs von hier aufgerufen wird, auf) Definiert über die Menge DFA 1: L1 = {Q1, E, D1, s1, F} DFA 2: L2 = {Q2, E, D2, s2, F}

Q ist die Liste der Staaten. Ex 1, 2, 3, 4 oder a, b, c, d

E ist die Sprache Ex. 0, 1

D ist der Übergang eingestellt Bsp. {(A, 0, b)} Zustand a geht auf eine 0

b

s ist der Ausgangszustand

F ist der Endzustand

Wie würden Sie nehmen und Exklusiv-Oder zweier DFAs L1 und L2

Answer 1

Q = Q1 Q2 X;

E = E;

D alle Übergänge, die von beiden Systemen übereinstimmen;

s = S1 intersect S2;

F = F1 XOR F2

Answer 2

Hier sind ein paar breiten Hinweise zum Einstieg ...

Sie werden wahrscheinlich einen anderen DFA, deren Zustände Q3 bauen wollen, werden identifiziert mit Elemente des kartesischen Produkts von Q1 und Q2. Von s1 und s2, sollte es sein ziemlich offensichtlich, welches Element von Q3 sollte als Startzustand bezeichnet werden.
Dann, da jeder Knoten (n1 in Q1, n2 in Q2) in Q3, sollte es ziemlich einfach sein, herauszufinden, wo die Kanten für jeden Eingang gehen müssen. Und F3 wird eine Reihe von Staaten (N1, n2), wobei (n1 in F1 XOR n2 in F2) hält.