# 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$? Aug 27, 2014 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, 2014 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, 2014 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). Aug 31, 2014 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. Aug 31, 2014 at 15:06

There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $$n$$ accepted by a NFA in the general case (without restricting to the acyclic NFA case).