Unreachable states

A finite automaton may have states that cannot be reached. We call such states unreachable states. We typically want to remove them, because they only make the whole automaton needlessly complicated.

Example of unreachable states

Take this automaton:

We can see that whatever we do, we never get to state q₃, because no transition leads into it. We say that state q₃ is unreachable. A question: would state q₃ be reachable if a transition from another state led into it? If we drew an edge from one of the states q₀, q₁, q₂, q₅, it would be reachable. If we added another node and drew a transition from it…

…then of course both states q₃ and q₄ would be unreachable.

Definition of an unreachable state

First we define a reachable state. Take a finite automaton A = ⟨Q, Σ, δ, q₀, F⟩. We say that a state q ∈ Q is reachable if there exists a string w ∈ Σ^∗ such that

$$⟨q_0,w⟩{\mapsto }^{\ast }⟨q,\epsilon ⟩.$$

A state q ∈ Q is unreachable if it is not reachable.

How to remove unreachable states

If an automaton already has some unreachable states, it is a good idea to remove them. We construct an equivalent automaton A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ that has no unreachable states.

We build the set of reachable states iteratively. We start with the set S₀ = {q₀}, because the start state is certainly reachable. We build the next set like this:

$$S_i=\{r|\delta (q,a)=r\text{ for some }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

In plain words, the set S₀ is always given, and we build the set S₁ by taking all the states in the set S₀ and finding where the transitions for all the symbols of Σ lead. We take the union of these states and the original set of states S₀. We find the set S₂ and the following sets in the same way. Clearly S_{i − 1} ⊆ S_i.

We can then obtain the set of reachable states like this:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

It may look strange that we are trying to take the union of infinitely many sets S_i, but the automaton has only a finite number of states. This means that at some point the sets S_j and S_{j + 1} and all the following ones will be the same, so even after taking the union of infinitely many sets we can get a finite set of states.

Let’s go back to the automaton

and try to find the set of reachable states. We start by stating the basic equality

$$S_0=\left\{q_0\right\}$$

Now we work out the set S₁. We have to find all the transitions from state q₀ and add their target states to the set S₀. Because q₀ → ^a q₁ and q₀ → ^bq₂, the set S₁ will additionally contain the states q₁ and q₂:

$$S_1=\{q_0,q_1,q_2\}$$

Next we construct the set S₂. We look at where we can get to from the states q₀, q₁, q₂. The only new state is q₅, which we can reach from state q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Next we build the set S₃. Can we get to any new state from the states q₀, q₁, q₂, q₅? We cannot, so the set S₃ will contain the same elements as S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Because S₂ = S₃, we also have S₃ = S₄ = S₅ = … If we take the union of all the S_i, we get the set S₂, because no further element is added in any later set.

So the set of reachable states of the automaton is {q₀, q₁, q₂, q₅}. We get the unreachable states by a simple set difference:

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

The set of unreachable states of our automaton is {q₃, q₄}. We remove from the automaton A all the unreachable states and all the transitions that involved an unreachable state. That is, we define the equivalent automaton A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ without unreachable states for the automaton A = ⟨Q, Σ, δ, q₀, F⟩ as:

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
• $F^{\prime }=F\cap Q^{\prime }=F\cap \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$

Sources

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