title: How do you construct the union of two DFA's?
body: <p>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</p>
  
  <pre><code>{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
  </code></pre>
  
  <p>I have a resulting transition table showing the union as:</p>
  
  <pre><code>delta | 0  | 1 
  ----------------
    Aa  | Ba | Bb
  ----------------
    Ab  | Bb | Ba
  ----------------
    Ba  | Aa | Ab
  ----------------
    Bb  | Ab | Aa
  </code></pre>
  
  <p>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?</p>