Removing Useless States From Finite State Automata
Algorithm
Starting from certain states in a finite state automaton
once can never reach a final state. Therefore, removing these
states will not make any difference to the language accepted by
the automaton. These states are called useless states.
The algorithm is quite straightforward. Rather than constructing the
set of useless states, we will calculate its complement: the set of
useful states. Clearly, all final states are useful. Similarly, any
state which has a transition to a useful state is, itself useful.
The algorithm basically repeats this step until no new useful states
are discovered.
- Initialise the set of useful states U to
the set of final states.
- Calculate the set of states M which can go to a state in U
in one step. Thus M will include all states q such
that for some input symbol a and state q' in
U, (q,a)
q'
is a production rule.
- Update U to be the union of M and the old value
of U.
- If new elements have been added to U in the last step,
jump to step 2.
- Remove all states in the automaton not in the final value of
U and transitions from or into them.
- If the initial state has been removed, add a new state with no
related transitions and set it to be the initial state.
Note that the last step is necessary since any finite state
automaton requires to have an initial state.
Example
Consider the following finite state automaton:
- Initialise the set of useful states to the final states:
U={ A }
- Calculate the set M of all states which can go to a
state in {A} in one transition:
M={ S, A }
- Update U by taking the union of its old value to
that of M:
U={ A } U { S, A } = { S, A }
- U has changed value and we therefore jump back step 2 of the
algorithm. Calculate the set M of all states which can go
to a state in {S, A} in one transition:
M={ S, A }
- Update U by taking the union of its old value to
that of M:
U={ S, A } U { S, A } = { S, A }
- Since no new elements have been added to U, we can now calculate
the set of useless states by taking the complement of U:
{ B, C }
- Remove all useless states (and related transitions) from the automaton:
- The automaton still has an initial state and is therefore valid.
Exercises
Remove the useless states from the following automata:
-
-