Removing Unreachable States From Finite State Automata

Algorithm

A state q' is said to be reachable from another state q if, there in an input string which may take us from state q to state q'.

Certain states in a finite state automaton are not reachable from the initial state. These states are called unreachable states and can be removed from the automaton without changing the accepted language.

The algorithm is quite straightforward. Rather than constructing the set of unreachable states, we will calculate its complement: the set of reachable states. Clearly, the initial state is reachable. Also, any state which is the destination of a transition from a reachable state is itself reachable. The algorithm basically repeats this step until no new reachable states are discovered.

1. Initialise the set of reachable states R to the set containing only the initial state.
2. Calculate the set of states M which can be reached from a state in R in one transition. Thus M will include all states q' such that for some input symbol a and state q in R, (q,a) q' is a production rule.
3. Update R to be the union of M and the old value of R.
4. If new elements have been added to R in the last step, jump to step 2.
5. Remove all states in the automaton not in the final value of R and transitions from or into them.

Example

Consider the following finite state automaton:

1. Initialise the set of reachable states R to the set containing only the initial state

   R={ S }

2. Calculate the set of states M which can be reached from a state in { S } in one transition:

   M={ A }

3. Update R to be the union of M and the old value of R:

   R = { A } U { S } = { S, A }

4. R has changed value and we therefore jump back step 2 of the algorithm. The set of states M which can be reached from a state in { S, A } in one transition is:

   M={ S, A, B }

5. Update R to be the union of M and the old value of R:

   R = { S, A, B } U { S, A } = { S, A, B }

6. R has changed value again and we therefore jump back step 2 of the algorithm. The set of states M which can be reached from a state in { S, A, B } in one transition is:

   M={ S, A, B }

7. Update R to be the union of M and the old value of R:

   R = { S, A, B } U { S, A, B } = { S, A, B }

8. Since no new elements have been added to R, we have now calculated the set of reachable states. To remove unreachable states, we just remove the states in the complement of R:

   

   Exercises

   Remove the unreachable states from the following automata:

   1. 
   2.