# Deleting useless (dead) states from a finite automaton

A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the useful states is trivial: Let $G$ be the set of good (useful) states and let $\Omega$ be the set of all states. Initialize $G$ with all final states. Check all states $\Omega\setminus G$ for those that have a transition to a state in $G$ and add them to $G$. Repeat until nothing is added to $G$ any more.

A straightforward implementation mimicking the above, however, can be quite costly, looping over states and transitions over and over again. The number of loops checking $\Omega \setminus G$ is limited by the depth.

In a degenerate automaton containing transitions $a_0\to a_1 \to\dots\to a_n\to f$ where $f$ is a single final state and an additional transition $a_n\to u$ such that $u$ is useless, there would be around $n$ loops if you always loop over the $a_i$ in the order of $i$. But if you loop in decreasing order of $i$ shuffling found good states immediately into $G$, a single loop would suffice.

But this may lead to other degenerate situations (I am guessing).

I am looking for an algorithm to mark useful states, or remove useless states, that is not recursive (to prevent stack overflow, since I am looking at FAs with millions of states) and as efficient as possible.

Extra question: are there theoretical limits known for this algorithm?

• Your proposed algorithm doesn't remove all useless states. Consider the case where there is an accepting state that is unreachable from the initial state: your algorithm will keep that accepting state and all states that can reach it. – David Richerby Nov 22 '15 at 16:19
• Finite state automaton with disconnected states? Hmm, yes, theoretically this is not forbidden. I did not look up a proof, but I would think that the Thompson construction does not create disconnected states. Neither does the subset construction to create the DFA. Or does it? – Harald Nov 22 '15 at 16:33
• The subset construction certainly can. Let the state set of your NFA be $Q$, with initial state $q_0$. The subset construction gives you the state set $\mathcal{P}(Q)$ but any state that is not of the form "the set of states the NFA can be in after reading input $w$ when starting in $q_0$" is unreachable. I don't think the Thompson construction will give disconnected states but I've not checked the details on that. – David Richerby Nov 22 '15 at 16:37