Creating an Exclusive Or from two Deterministic Finite Automatons (Deterministic Finite-State Machines)

Question

Two DFAs (Deterministic Finite Automaton or Deterministic Fininte-State Machines - Which will be called DFAs from here on) Defined over the set DFA 1: L1 = {Q1, E, D1, s1, F} DFA 2: L2 = {Q2, E, D2, s2, F}

Q is the list of states. Ex 1, 2, 3, 4 or a, b, c, d

E is the the language Ex. 0, 1

D is the transition set Ex. {(a,0,b)} state a goes to b on a 0

s is the starting state

F is the final state

How would you take and exclusive-or of two DFAs L1 and L2

Answer 1

Q = Q1 X Q2;

E = E;

D is all transitions that agree from both systems;

s = S1 intersect S2;

F = F1 XOR F2

Answer 2

Here are a few broad hints to get you started...

You'll probably want to build another DFA whose states Q3 are identified with elements of the Cartesian product of Q1 and Q2. From s1 and s2, it should be pretty obvious which element of Q3 should be designated as the start state.
Then, given any node (n1 in Q1, n2 in Q2) in Q3, it should be pretty easy to figure out where the edges need to go for each input. And F3 will a set of states (n1, n2) where (n1 in F1 XOR n2 in F2) holds.