I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires exponential time.

I would appreciate any help, Thanks in advance..

  • $\begingroup$ There's a standard construction that converts an NFA into a DFA, which you should be familiar with. You can't just convert the given NFA to a DFA because that would take exponential time. But think about how that translation works and how you could do it "on the fly", only translating the bare minimum as you go along. $\endgroup$ Dec 19 '13 at 17:30
  • $\begingroup$ i thought about keeping a binary string where the i-th bit represent if the machine can be in state (i-1) after each character read, is this more or less what you are implying? doesn't this can take exponential time as well? $\endgroup$
    – wipkiko
    Dec 19 '13 at 17:40
  • $\begingroup$ There's two processes at work here. Converting an NFA to a DFA takes exponential time in general, and could take exponential space for the resulting DFA. However, once you have that DFA, testing if a given string $w$ is accepted is now $O(|w|)$. The algorithm Yuval hints at below can test in polynomial (cubic or quartic if I remember correctly) time whether an NFA accepts a string $w$, without ever converting it to a DFA. If you have many strings that you're testing, you'll get the best speed if you do the DFA conversion, but if you're only testing a few strings, do the NFA algorithm. $\endgroup$
    – jmite
    Dec 19 '13 at 18:14
  • $\begingroup$ possible duplicate of Is every regular language Turing-decidable, and how can we prove this? $\endgroup$
    – D.W.
    Dec 19 '13 at 18:27
  • $\begingroup$ @wipkiko That's exactly what you need to do. It doesn't take exponential time because the number of steps of the automaton is equal to the number of characters in $w$ and each step can be simulated in polynomially many steps of the Turing machine. $\endgroup$ Dec 19 '13 at 19:13

Hint (expanding on David Richerby's hint): As the NFA reads $w$, keep track of the set of states it could be in at any given time.


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.