2
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Nov 22 '15 at 16:19
  • $\begingroup$ 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? $\endgroup$ – Harald Nov 22 '15 at 16:33
  • $\begingroup$ 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. $\endgroup$ – David Richerby Nov 22 '15 at 16:37
3
$\begingroup$

Reverse all edges in the graph, and add a new state pointing at all accepting states. Find the set of states reachable from the new state in linear time (using BFS/DFS). These are the useful states (according to your definition).

The running time of this algorithm is linear in the number of states plus number of transitions. This is about the best you can hope for (in terms of asymptotic worst-case running time).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yeah, well, I would say that "reverse the edges" gets the same status as the original algorithm: theoretically trivial, the practical implementations I can think of are inefficient and ugly. Any hints to literature about the complexity? $\endgroup$ – Harald Nov 22 '15 at 13:09
  • 2
    $\begingroup$ @Harald Depending on your graph representation, you don't have to do anything explicitly. Just use BFS or DFS -- you can't get much faster than that. (Btw, you can also eliminate states that are not reachable from the initial state in this fashion.) $\endgroup$ – Raphael♦ Nov 22 '15 at 13:23
  • $\begingroup$ My graph representation has only forward pointers, and it is pointers (Java object reference) nothing array based. I am thinking about creating an overlay graph where each node references a node of the original graph as well as the backward pointers. Problem is that I cannot store additional information in the available nodes, so every bit I need to control the algorithm needs a lookup of the node in a hash map. The nodes are kept small in memory for the final DFA outcome. This makes graph algorithms slightly cumbersome. $\endgroup$ – Harald Nov 22 '15 at 13:40
  • 1
    $\begingroup$ At this point this is a programming question, not an algorithmic question. Perhaps you should change your data structure. $\endgroup$ – Yuval Filmus Nov 22 '15 at 13:42
  • $\begingroup$ @Harald, I've edited the answer to explain the running time. "inefficient" - actually, Yuval's algorithm is efficient: as efficient as you could hope for, asymptotically. "ugly" - well, I guess beauty is in the eye of the beholder. I find the algorithm elegant. As Yuval, says the remaining concerns about data representation are a data structures question, not an algorithm question, and as none of that is in the original question, this is now out of scope for answering the question that was asked. $\endgroup$ – D.W.♦ Nov 23 '15 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.