Total DFA

The last type of FSA that we need to look at is the total DFA - this has properties which we will need in the next section.

A total FSA is one where each state has exactly one transition to some other state for every input symbol. Thus there are no ``gaps'' in the transition table for the machine: given any state and any input symbol, it will always be possible to make a transition.

We can convert any ordinary DFA to a total DFA as follows:

1. Create some new state $S$, which we will use for ``stuck'' computations
2. For each input symbol, make a transition from state $S$ to itself: thus it is never possible to leave this state.
3. For each other state $S'$, and for every possible input symbol $a$, check to see if $S'$ has an outgoing transition on $a$; if it doesn't, then make a new transition from $S'$ to $S$ on $a$.

It can be easily seen that this DFA is total.