How do you union of two finite automata as well as establish the transition table for it. I'm unsure of how to properly union the two finite automata. I believe the transition table would look something like this:

state | a | b | a,b

x1|  x2 |  x3 | 
x2|     |     |  x3
x3|     |     |  x3
y1|  y2 |  y3 |     
y2|     |     |  y3
y3|     |     |  y3 

I'm to sure how to properly develop the FA for these two diagrams. I would appreciate any links or advice on how to go about this.

enter image description here


1 Answer 1


Hint from "Introduction to the Theory of Computation" by Michael Sipser (bible of theory of computation):

"We construct $M$ from $M_1$ and $M_2$ (the two original DFAs). To keep track of both simulation with finite memory you need to remember the state that each machine would be in if it had read up to this point in the input. Therefore you need to remember a pair of states...."

Initial states:

The start state will be a state constructed from the two original start states, i.e



What happens with input $a$?

Let's examine the two original automata:

$x_1$ can transition to $x_2$

$y_1$ can transition to $y_3$

Due to these facts we make the transition $\delta((x_1,y_1),a) = (x_2,y_3)$.

Final/Accepting states:

Any state pair $(x_i,y_j)$ where $x_i$ was an accepting state in automata 1, or $y_j$ was an accepting state in automata 2, i.e any state where $x_2$ or $y_2$ is mentioned.

One consequence is that the state we created a transition to i.e $(x_2,y_3)$, will be an accepting state.

  • $\begingroup$ Hey Anders, thanks for the reply. By accepting state, do you mean final state? $\endgroup$
    – Tabrock
    Jan 28, 2015 at 21:17
  • 1
    $\begingroup$ No, I mean accepting states, but I guess final states are also used in literature. Answer updated to include both. $\endgroup$
    – User
    Jan 28, 2015 at 21:18
  • $\begingroup$ Hey! "bible of theory of computation" that is Hopcroft and Ullman! $\endgroup$ Jan 13, 2016 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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