11
$\begingroup$

Let $M$ be an acyclic NFA.

Since $M$ is acyclic, $L(M)$ is finite.

In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete.

The second answer for that question provides a counting algorithm, but only works for unambiguous NFAs (where every word is accepted by at most a single path).

Given an NFA $M$, can we approximate $|L(M)|$ in polynomial time?


As automata is a highly studied subject, I was surprised that I couldn't find anything about this, so if someone knows of a reference it'll be great :).

$\endgroup$
  • $\begingroup$ The word "acyclic" doesn't appear in the linked question. Who suggested that computing $|L(M)|$ is #P-hard for an acyclic NFA $M$? $\endgroup$ – Tyson Williams Aug 27 '14 at 21:31
  • $\begingroup$ @TysonWilliams - it came up in the comment of the second answer. I'm not sure this is based on anything and this is why I used the word "suggested". $\endgroup$ – R B Aug 27 '14 at 21:44
  • $\begingroup$ @TysonWilliams - In order for the question to make sense you either deal with acyclic automatons or count the words up to a given length. Dealing with acyclic automatons is easier, as you can find the limit on the word length and use the other algorithm. $\endgroup$ – R B Aug 27 '14 at 21:46
  • 1
    $\begingroup$ As for the “suggested” part, the exact counting is indeed #P-complete. Membership to #P is clear, and #P-hardness can be shown by a simple reduction from the DNF counting problem (i.e., the problem of counting the number of satisfying assignments for a given DNF formula). $\endgroup$ – Tsuyoshi Ito Aug 31 '14 at 12:47
  • 3
    $\begingroup$ Now I noticed that you had already posted the same question on cs.stackexchange.com and had already received an answer before posting the question here. I have to wonder why you posted this question here without revealing these facts. $\endgroup$ – Tsuyoshi Ito Aug 31 '14 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.