In a DFA, does every state have a transition on every symbol of the alphabet?

Question Detail: 

If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?

Asked By : Duncan

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12587

Answered By : Wandering Logic

You seem to have stumbled on a contentious issue. Apparently computer scientists like to argue. I certainly like to argue, so here goes!

My answer is an unequivocal: No. A deterministic finite automata does not need a transition from every state for every symbol. The meaning when $\delta(q,a)$ does not exist is simply that the DFA does not accept the input string.

While you can create a definition of DFA that requires that $\delta(q,a)$ does exist, it is simply not the case that a missing transition makes the resulting structure (whatever you call it) in any way nondeterministic as many of the commenters are claiming. If you are taking a course on automata theory then the next topic will be context-free languages and push-down automata where the distinction between nondeterministic and deterministic automata is crtical, and you need to use the correct definition of non-determinism.

Non-determinism is associated with having more than one legal transition.

I think we all agree with the following Wikipedia definition (which I'll show in just a second is slightly ambiguous):

A deterministic finite automaton $M$ is a 5-tuple, ($Q$, $\Sigma$, $\delta$, $q_0$, $F$), consisting of

1. a finite set of states ($Q$)
2. a finite set of input symbols called the alphabet ($\Sigma$)
3. a transition function ($\delta : Q \times \Sigma \rightarrow Q$)
4. a start state ($q_0 \in Q)$
5. a set of accept states ($F \subseteq Q$).

Let $w = a_1 a_2 \cdots a_n$ be a string over the alphabet $\Sigma$. The automaton $M$ accepts the string $w$ if a sequence of states, $r_0, r_1, \ldots, r_n$, exists in $Q$ with the following conditions:

1. $r_0 = q_0$
2. $r_{i+1} = \delta(r_i, a_{i+1})$, for $i = 0, \ldots, n−1$
3. $r_n \in F$.

The ambiguity, and the controversy is over the defintion of the transition function, $\delta$ (number "3" in the first bulleted list.) We all agree that what differentiates a DFA from an NFA is that $\delta$ is a function rather than a relation. But is $\delta$ a partial function or a total function?

The definition of the DFA works just fine if $\delta$ is a partial function. Given an input string, if you reach a state $q_i$ with an input symbol $a_j$ where there is no next state then the automata simply does not accept.

Moreover when you extend this definition to create the definition of push-down automata it will be the case that you must make the distinction that push-down automata with transition functions that are partial functions are classified as deterministic, not nondeterministic.

If the partial function bothers you then here is a trivial transformation that makes $\delta$ a total function. (This transformation is not like the subset construction algorithm, it adds at most O(1) states, is linear in the original number of states, and can be extended to work with PDAs. None of those facts is true of the subset construction algorithm.)

1. add a state $q_{\mathrm{error}}$
2. for every pair $(q_i, s_j)$ where $\delta$ is undefined, define $\delta(q_i, s_j) = q_{\mathrm{error}}$.

This automata has a $\delta$ that is a total function and accepts and rejects exactly the same set of states that your original automata accepted and rejected.