Making a Finite State Automata Total

Algorithm

A FSA is said to be total if from any state, there is at least one outgoing transition for every input symbol.

1. Add a new state Z (or whatever, as long as the name has not yet been used)
2. If for a state A, there is no outgoing transition with terminal symbol a, we add a transition fron A to Z with input a.

Example

Consider the following FSA:

1. We add a new state D0:

   

2. For every state A, terminal symbol a, such that there is no outgoing transition from A with terminal symbol a, we add a transition fron A to D0 with input a:

   

Exercises

Make the following FSA total: