Union of two finite automata?
Hint from &quot;Introduction to the Theory of Computation&quot; by Michael Sipser (bible of theory of computation):
&quot;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....&quot;
Initial states:
The start state will be a state constructed from the two original start states, i.e
$(x_1,y_1)$
Transitions:
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.