I recently discovered the idea of a total transition function in Automata Theory. To my understanding this means that every state has at least one outgoing state.

My question is whether this restriction applies to accepting states, since my initial intuition tells me that this would be an overly strict enforcement of the state machine.

Thanks in advance for any answers.

  • $\begingroup$ Why should it not apply? $\endgroup$ – pzp Feb 23 '17 at 6:01
  • $\begingroup$ Purely for the fact that including them does not seem to add value to the property. In my (admittedly naive) opinion, total transition functions are most useful in preventing the occurrence of dead states, since these signify errors in the modeling of languages and state machines. Accepting states are of course a special case of this. Otherwise, does making the statement that a transition function is total, only exist as a classification criteria? $\endgroup$ – Regan Koopmans Feb 23 '17 at 6:25
  • 2
    $\begingroup$ Do you suggest that accepting states are a special case of dead states, i.e., without outgoing edges? Probably you got this impression as accepting states are also called final states in some texts. They are however not final in the sense that computation cannot proceed from there. These states are not the last state of the automaton, but the accepting states are more like flags, that indicate whether a computation is accepting if the last state in the computation happens to end on such a state. During a computation we can happily pass as many final/accepting states as we like. $\endgroup$ – Hendrik Jan Feb 23 '17 at 20:56

Unfortunately there seem to be several different definitions of DFAs in the literature. Here is the classical definition:

A DFA is a quintuple $\langle \Sigma,Q,q_0,F,\delta \rangle$, where $\Sigma,Q$ are non-empty finite sets, $q_0 \in Q$, $F \subseteq Q$, and $\delta \colon Q \times \Sigma \to Q$.

We extend $\delta$ to a function $\hat\delta \colon Q \times \Sigma^* \to Q$ using the recurrence $\hat\delta(q,w\sigma) = \delta(\hat\delta(q,w),\sigma)$, with base case $\hat\delta(q,\epsilon)=q$.

The language accepted by the DFA is $\{ w \in \Sigma^* : \hat\delta(q_0,w) \in F \}$.

Other definitions are possible. For example, you might allow $\delta$ to be a partial function. However, the definition I stated has a significant advantage: the Myhill–Nerode theorem holds for it.

Under my definition, from each state there is exactly one transition for each alphabet symbol. Other definitions could be different. Only you know which definition you use.

It is important to stress that this "strict" definition doesn't restrict the power of DFAs one bit. It is known that DFAs accept the very same languages as NFAs, for example, though there could be a dramatic difference in state complexity (the number of states needed to accept a given language).


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.