Redundant states

A finite automaton may have states from which it is impossible to reach an accepting state, so they serve no purpose. We call such states redundant states. We usually want to remove them, because they only complicate the automaton unnecessarily.

Example of redundant states

Let us take this finite automaton:

We can see that once we get into state q₄ or q₅, we can never reach one of the accepting states q₁ or q₂. Such states are redundant and we can simply remove them, which gives us a new automaton that is equivalent; it accepts the same language. After deleting the redundant states, the automaton would look like this:

It accepts the same language. However, there are times when it is useful to keep some redundant states, for example when we construct a complete automaton.

Definition of a redundant state

Let A = ⟨Q, Σ, δ, q₀, F⟩ be a finite automaton. We say that a state q ∈ Q is redundant if there is no string w ∈ Σ^∗ and no state q_f ∈ F such that

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

How to remove redundant states

We assume that the input is an automaton A = ⟨Q, Σ, δ, q₀, F⟩ that already has no unreachable states. We gradually find the states that lead to accepting states, then the states that lead to states that lead to accepting states, and so on. This gives us the set of all states that are not redundant. At the start we put S₀ = F. We then construct further sets S_i for i ∈ ℤ⁺ by this rule:

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

The resulting set of all states that are not redundant can be expressed like this:

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

And the set of redundant states as

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

In other words: if S_i = S_{i + 1}, then the set Q ∖ S_i contains the redundant states. We will illustrate the procedure on this automaton:

First we set S₀ = {q₁, q₂}. Next we build the set S₁ by adding to S₀ all states that lead to one of the states in S₀. So we add the states q₀ and q₃, because there is a transition from q₀ to q₁ and from q₃ to q₂. We get S₁ = {q₀, q₁, q₂, q₃}. Since S₀ ≠ S₁, we carry on.

We build the set S₂. So we look for all states from which we can get into S₁ and which are not in S₁ yet. There is only one, q₆, from which we can get into the state q₃. We get S₂ = {q₀, q₁, q₂, q₃, q₆}. Since S₁ ≠ S₂, we carry on.

We build the set S₃. Is there a new state from which we can get into some state in S₂? There is not: from the states q₄ and q₅ we cannot get into any of the states in S₂, and all the other states are already in S₂. So S₃ = {q₀, q₁, q₂, q₃, q₆}. Since S₂ = S₃, the algorithm stops and the set S₂ is the set of states that are not redundant. The set {q₄, q₅} is the set of redundant states.

Formally, we construct a new equivalent automaton without redundant states as follows. We have an automaton A = ⟨Q, Σ, δ, q₀, F⟩ and we build from it an equivalent automaton A′ = ⟨Q′, Σ, δ′, q₀, F⟩ without redundant states.

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

Sources

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