2
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\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$
    – David Richerby
    Commented Dec 19, 2013 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
    Commented Dec 19, 2013 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$
    – Joey Eremondi
    Commented Dec 19, 2013 at 18:14
  • $\begingroup$ possible duplicate of Is every regular language Turing-decidable, and how can we prove this? $\endgroup$
    – D.W. ♦
    Commented Dec 19, 2013 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$
    – David Richerby
    Commented Dec 19, 2013 at 19:13

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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