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.

  • 1
    $\begingroup$ What do you mean by $\delta(r,a)=\emptyset$ ? does it mean lack of transition from state $r$ upon reading the character $a$? $\endgroup$ – Ariel Oct 19 '16 at 17:50
  • $\begingroup$ @Ariel Yes, that what is meant by $\emptyset$. At least that is how I see it. $\endgroup$ – user913923219 Oct 19 '16 at 17:53
  • $\begingroup$ 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. $\endgroup$ – user253751 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.

  • $\begingroup$ 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? $\endgroup$ – user913923219 Oct 19 '16 at 19:48
  • $\begingroup$ If you define DFA as above, then yes. $\endgroup$ – Ariel Oct 19 '16 at 19:53

The transition function of a DFA gets a state and a symbol and outputs a state. It cannot output the empty set. That would be a type mismatch. In other words, in a DFA, every state has an outgoing transition for every symbol – exactly one, in fact.

You can define an "extended" DFA in which some transitions are allowed to be missing, but you would then need to modify the definition of the product DFA. It is a good exercise to see what the appropriate modification would be.


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.