Efficient simulation of an NFA, while preserving the paths to the accept states

Question

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?

Answer 1

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)$.

Answer 2

(I know I'm 4 years late, but I think I have a better solution than the one accepted.)

You rarely want to build the full DFA from an NFA since the number of states in the DFA can be exponentially larger. You might want to look up the Thompson's NFA algorithm for simulating an NFA in linear time.

In short, you parse the input string one symbol at a time, and at each step you have a set of active states. The new set of active states is the union of all the reachable states from each of the current states. The string matches if an accepting state is active when you reach the end of the input string.

Your problem seems pretty equivalent to tracking submatches in a regular expression, which can be done in linear time at the cost of an $O(n^2)$ memory usage.

The idea would be to attach to each active state one path that lead to this state. When a state is reachable from two distinct path, you pick either one of them. This path selection is what prevents the exponential blow from happening. In the worst case, each state is active and has to store a path through all the states, hence an $O(n^2)$ memory requirement. But the run time is not modified.