Redundant states
Kapitoly: Unreachable states, Redundant states, Minimizing the automaton
A finite automaton can have states that are impossible to get from to a finite state and so are useless. We call such states unreachable states. We typically want to remove these states because they only unnecessarily complicate the automaton.
Example of redundant states
Consider this finite automaton:
We can see that the moment we reach the states q4 or q5, we can never reach one of the finite states q1 or q2. Such states are so redundant that we can simply remove them, which would give us a new automaton, but one that is equivalent; it would accept the same language. After deleting the redundant states, the automaton would look like this:
It would accept the same language. However, there are times when it is appropriate to have some redundant states - for example, when constructing a total automaton.
Definition of a redundant state
Consider a finite automaton $A=\left<Q, \Sigma, \delta, q_0, F\right>$. We say that a state q ∈ Q is redundant if there is no word $w \in \Sigma^+$ and no state qf ∈ F such that
$$ \left<q, w\right>\mapsto^\ast\left<q_f,\varepsilon\right>. $$
How to remove redundant states
Suppose that we have an automaton $A=\left<Q, \Sigma, \delta, q_0, F\right>$, which is already free of unreachable states, as input. We will successively find states that lead to end states, and then states that lead to states that lead to end states, and so on and on. This gives us the set of all states that are not redundant. We start with S0 = F. We will construct other sets Si for i ∈ ℕ according to this prescription:
$$ S_i = \left\{q,|,\forall q \in Q, a \in \Sigma:\quad \delta(q, a)\in S_{i-1}\right\}\cup S_{i-1} $$
The resulting set of all states that are not redundant can be expressed as follows:
$$ \bigcup_{i=1}^{\infty}S_i. $$
And the set of redundant states as
$$ Q \setminus \bigcup_{i=1}^{\infty}S_i. $$
In other words, if Si = Si + 1 holds, then the set Q∖ Si contains redundant states. We will illustrate the procedure with the following automaton:
First, we set S0 = {q1, q2}. Next, we construct the set S1 by adding to the set S0 all the states that lead to one of the states in the set S0. Thus, we add the states q0 and q3, since q0 leads to q1 and q3 leads to q2. We get S1 = {q0, q1, q2, q3}. Since S0 ≠ S1, we proceed further.
We construct the set S2. Thus, we look for all the states from which we can get to S1 and yet are not in S1. There is a single state, q6, from which we can get to q3. We get S2 = {q0, q1, q2, q3, q6}. Since S1≠ S2, we continue on.
We construct the set S3. Is there a new state from which one can get to any of the states in S2? There isn't, from the states q4 and q5 you can't get to any of the states in S2 and the other states are already in S2. Thus, it is true that S3 = {q0, q1, q2, q3, q6}. Since S2 = S3, the algorithm terminates and the set S2 represents the set of states that are not redundant. The set {q4, q5} is the set of states that are redundant.
Formally, we construct a new equivalent automaton without redundant symbols as follows. We have an automaton $A=\left<Q, \Sigma, \delta, q_0, F\right>$ and build an equivalent automaton $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F\right>$ to it without redundant symbols.
- $Q^\prime = Q \setminus \bigcup_{i=1}^\infty S_i$
- $\forall q \in Q^\prime, a\in \Sigma:\quad \delta^\prime(q, a) = \delta(q, a)$