[Solved]: Efficient simulation of an NFA, while preserving the paths to the accept states

Problem Detail: 

The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup.

However, for my purpose I need to know which paths the NFA went through for accepted words. This is obviously not trivial if I simply use the subset construction method. The NFA could also have $\epsilon$ transitions.

Of course, any such simulation could have a bad worst-case, in which there are a humongous amount of ways that the automaton could accept a given word. However, it'd be nice to have some sort of algorithm that runs, in, say, $O(m+n)$ for a word of length $m$ that the NFA has $n$ ways of accepting.

Is there any efficient way to do this?

Asked By : user54609

Answered By : Yuval Filmus

There is no need to construct the DFA. Instead, you can construct a dynamic programming table which answers the question "the NFA could be at state $s$ after reading the $k$th prefix of the word" (the parameters are both $s$ and $k$). In order to efficiently fill this table in the presence of $\epsilon$-transitions, you need to compute ahead of time the transitive closure of the $\epsilon$-transitions. As you fill the table, you can include data that will allow you to reconstruct at least some of the accepting paths (or all of them, if you insist, though it will be more tricky to handle the $\epsilon$-transitions). The running time, however, won't be linear but more like $O(q^2m)$, where $q$ is the number of states; perhaps you could optimize this further for sparse NFAs, but probably not to $O(m+n)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32929