Complete automaton

In the basic definition of a finite-state machine there does not have to be a transition from every state for every symbol. A complete automaton is an automaton that has transitions defined from every state for every symbol of the input alphabet.

How to construct a complete automaton

Take this automaton A = ⟨Q, Σ, δ, q₀, F⟩:

The transition from the state q₀ for the letter “b” is not drawn. If such a situation occurs, we say that the automaton does not accept the input string. However, from the point of view of formalisation it may not be convenient for the transition function δ to be undefined for some values; here, for example, δ(q₀, b) is not defined.

This is easy to fix by constructing an equivalent automaton with one extra state – the “missing” transitions will lead to this state, it will not be an accepting state and all further inputs will just loop in it. We call this automaton a complete automaton. The modified equivalent automaton could look like this:

We have added the state q_fail. From the other states we added a transition to it exactly when there was no transition there before. This state is not accepting and loops for all further inputs. So where we met a missing transition in the previous automaton, there is no missing transition here and the automaton would end up in the state q_fail.

So we can always assume, without loss of generality, that an automaton has transitions defined for all combinations of states and symbols of the alphabet.

Definition

For a complete automaton A = ⟨Q, Σ, δ, q₀, F⟩ we therefore have

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

Sources

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