1

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

2 Answers 2

0

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.

0

Q = Q1 X Q2;

E = E;

D is all transitions that agree from both systems;

s = S1 intersect S2;

F = F1 XOR F2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.