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
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.
Q = Q1 X Q2;
E = E;
D is all transitions that agree from both systems;
s = S1 intersect S2;
F = F1 XOR F2