# The transition function of the union of regular languages

I follow Michael Sipser's book, "Introduction to the Theory of Computation". To be specific, I am trying to understand the proof about the union of regular languages. However, I have a problem grasping how exactly the transition function is defined. The book says that for each $(r_1, r_2) \in Q$ and each $a \in\sum$, let $\delta((r_1, r_2),a) = (\delta_1(r_1, a), \delta_2(r_2,a))$. The problem is that I cannot understand what happens if, for example, $\delta_2(r_2,a) = \emptyset$ and $\delta_1(r_1, a) = q_1$ and I get $\delta((r_1, r_2),a) = (q_1, \emptyset)$, which does not belong to the set of all pairs of states.

• What do you mean by $\delta(r,a)=\emptyset$ ? does it mean lack of transition from state $r$ upon reading the character $a$? Oct 19 '16 at 17:50
• @Ariel Yes, that what is meant by $\emptyset$. At least that is how I see it. Oct 19 '16 at 17:53
• is $\emptyset$ a state? If $\emptyset$ is a state, then you have no problem. If $\emptyset$ is not a state, then $\delta_1(r_2,a) = \emptyset$ is impossible because the range of $\delta_1$ is (a subset of) the set of states. Oct 19 '16 at 22:09

In the definition of a deterministic finite automaton, we require that the transition function $\delta$ is well defined on all of $Q\times\Sigma$, i.e. $\delta: Q\times \Sigma\rightarrow Q$. Sometimes we allow omitting transitions, and say that the automaton is "stuck" if it stumbles upon this transition, however in Sipser's book he defines the transition function as above (defined on all of $Q\times\Sigma$).
If you insist on allowing the the automaton to get stuck, then this results in a slight modification of the proof. Instead of looking at $Q_1\times Q_2$ (where $Q_i$ is the state set of the $i'th$ automaton), consider the state space $\left(Q_1\cup\left\{\widehat{q_1}\right\}\right)\times\left(Q_1\cup\left\{\widehat{q_2}\right\}\right)$, where $\widehat{q_1},\widehat{q_2}$ are special states designed to deal with lack of transition. You can now complete the details yourself.
• Thank you for your answer. If I want to construct an automaton that recognizes only ${0}$ over the alphabet ${0,1}$, then I have to include transitions for $1$ somehow. Is that correct? Do transitions for $1$ have to lead to some state from which there is no escape? Oct 19 '16 at 19:48