# Can we approximate the number of words accepted by an NFA?

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

• The word "acyclic" doesn't appear in the linked question. Who suggested that computing $|L(M)|$ is #P-hard for an acyclic NFA $M$? – Tyson Williams Aug 27 '14 at 21:31
• @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". – R B Aug 27 '14 at 21:44
• @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. – R B Aug 27 '14 at 21:46
• 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). – Tsuyoshi Ito Aug 31 '14 at 12:47
• 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. – Tsuyoshi Ito Aug 31 '14 at 15:06