10
$\begingroup$

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.

$\endgroup$
3
  • $\begingroup$ No (not to our knowledge, at least). NFA equality is PSPACE-complete. See this discussion. $\endgroup$
    – Shaull
    Jun 11, 2013 at 17:29
  • $\begingroup$ @Shaull: The OP did not as for an efficient way. $\endgroup$
    – frafl
    Jun 11, 2013 at 17:31
  • $\begingroup$ @frafl: You are right. I assumed by "will take a long time" that the OP wants an efficient solution. Still, my comment mentions that it's in PSPACE, so it's decidable. $\endgroup$
    – Shaull
    Jun 11, 2013 at 18:03

1 Answer 1

10
$\begingroup$

The decision problem is PSPACE-complete as Shaull noted.

However, it turns out that in practice it is often possible to decide NFA equivalence reasonably quickly. Mayr and Clemente (based on experimental evidence) claim that the average-case complexity scales quadratically. Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions.

Just like SAT is NP-complete in a worst-case analysis, yet often turns out surprisingly tractable for real-world instances, it therefore seems likely that NFA equivalence can be decided efficiently for many real-world instances.

$\endgroup$

Your Answer

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

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