How do you construct the union of two DFA's?

Question

Does anyone have a straightforward description of the algorithm for constructing the union of two given DFA's? For example, say we have two DFA's over {0,1} where

{w|w has an odd number of characters}
  w has states A and B

delta | 0  | 1
----------------
  A   | B  | B
----------------
  B   | A  | A


{x|x has an even number of 1s}
  x has states a and b

delta | 0  | 1
----------------
  a   | a  | b
----------------
  b   | b  | a

I have a resulting transition table showing the union as:

delta | 0  | 1 
----------------
  Aa  | Ba | Bb
----------------
  Ab  | Bb | Ba
----------------
  Ba  | Aa | Ab
----------------
  Bb  | Ab | Aa

I have a pictorial solution in my lecture notes, but would like to see how others would describe it. From this, I can see that we essentially "multiply" these two original tables using their state values to result in a larger transition table. The DFA can be thus drawn from the resultant table. Does this sound right and should this work for all DFA cases, or is there something I'm missing?

Answer 1

The key to understand is that you have to run the two DFAs simultanously, or in general you have to maintain the states of both DFAs in the union DFA.

That's why you have to create the new states for the union DFA as a direct multiplication of the original states. This way you have a state for every combination of the states in original DFAs.

The transition rules for the new DFA can be directly calculated then. For example if you are in state Ab, and you get a 0 on input, the first DFA would go to state B and the second one to state b, so the union DFA's next state for this input will be Bb.

This method works in every case when you need to make a union of two or more DFAs. The resulting DFA may not be optimal, but later you can minimize it with any algorithm you like.