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?

Mirandamire

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.

Staten

What if you get a transition that is impossible in one of the automata? – Ralphralston

You would add E (error) state for the automaton that has impossible transition. That automaton would stay in that stat for the rest of the input sequence. Let's say it's the first one. You would then have Aa Ab, Ba, Bb, Ea, Eb states in the new automaton. – Bandore

I think it would be similar if one automaton only has {0,1} as input symbols, and the other has {1,2} as input symbols. We would then have to extend the both automatons with Error states (E for the first and e for the second) where 1st would go to E if 2 is the input, and 2nd would go to e state if 0 is the input. – Bandore