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?
