Total automaton

In the basic definition of a finite automaton, it is not necessary that there be a transition from all states to all symbols. A total automaton is an automaton that has defined transitions from all states for all symbols of the input alphabet.

How to construct a total automaton

Consider this automaton $A=\left<Q, \Sigma, \delta, q_0, F\right>$:

Here the transition from the state q₀ for the letter "b" is not drawn. If such a situation were to occur, we would say that the automaton does not accept the input word. However, from a formalization point of view, it may not be appropriate for the transition function δ not to be defined for some values; here, for example, it is not defined for δ(q₀, b).

This can easily be solved by constructing an equivalent automaton that has one extra state - the "missing" transitions will be directed to this state, this state will not be terminal, and all other inputs will already cycle in this state. We will call this automaton a total automaton. A modified equivalent automaton might look like this:

We have added the state $q_{\mbox{fail}}$. We have led a transition from other states to it just in case the transition did not exist there before. This state is non-terminal and cycles for all other inputs. Thus, if we encountered a missing transition in the previous automaton, there is no missing transition here and the automaton would go to the state $q_{\mbox{fail}}$.

Thus, we can always assume without loss of generality that the automaton has defined transitions for all combinations of states and alphabetic characters.

Definition of

Thus, for the total automaton $A=\left<Q, \Sigma, \delta, q_0, F\right>$, the following holds

$$ \forall q \in Q\quad \forall a \in \Sigma\quad \exists r \in Q:\quad \delta(q, a) = r. $$

Resources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools