<p>And now there is a faster FPRAS: <a href="https://arxiv.org/abs/2312.13320" rel="noreferrer">https://arxiv.org/abs/2312.13320</a></p>

CC BY-SA 4.0
2024-05-11T14:20:33.343Z
2024-05-11T14:20:33.343Z
Umang
<p>There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length <span class="math-container">$n$</span> accepted by a NFA in the general case (without restricting to the acyclic NFA case).</p>
<p>The result was published this year on STOC, by Arenas, Croquevielle, Jayaram and Riveros.</p>
<p>Here is the talk
<a href="https://youtu.be/tyK-uujHMLU" rel="noreferrer">https://youtu.be/tyK-uujHMLU</a>
and the paper
<a href="https://arxiv.org/abs/1906.09226" rel="noreferrer">https://arxiv.org/abs/1906.09226</a></p>

CC BY-SA 4.0
2021-11-08T02:23:40.693Z
2021-11-08T02:23:40.693Z
ricardorr
<p>Let <span class="math-container">$M$</span> be an acyclic NFA.</p>
<p>Since <span class="math-container">$M$</span> is acyclic, <span class="math-container">$L(M)$</span> is finite.</p>
<p>In a <a href="https://cstheory.stackexchange.com/questions/8200/counting-words-accepted-by-a-regular-grammar">related question</a>, it was suggested that exact counting of the number of words accepted by <span class="math-container">$M$</span> is <span class="math-container">$\#P$</span>-Complete.</p>
<p>The second answer for that question provides a counting algorithm, but only works for <em>unambiguous</em> NFAs (where every word is accepted by at most a single path).</p>
<blockquote>
<p>Given an NFA <span class="math-container">$M$</span>, can we approximate <span class="math-container">$|L(M)|$</span> in polynomial time?</p>
</blockquote>
<hr />
<p>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 :).</p>

CC BY-SA 3.0
2014-08-27T21:31:16.543Z
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
CC BY-SA 3.0
2014-08-27T21:44:48.167Z
@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
CC BY-SA 3.0
2014-08-27T21:46:08.287Z
@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
CC BY-SA 3.0
2014-08-29T17:57:09.630Z
I am fine with your use of "suggested", understand that it only makes sense to count something if it is finite, and agree that considering an acyclic state graph is easier.  I just don't see how this questions was suggested from the linked question.
Tyson Williams
CC BY-SA 3.0
2014-08-31T12:47:38.273Z
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
CC BY-SA 3.0
2014-08-31T15:06:25.460Z
Now I noticed that you had already posted the same question on [cs.stackexchange.com](http://cs.stackexchange.com/questions/28484/counting-the-number-of-words-accepted-by-an-acyclic-nfa) 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
<ds.algorithms><fl.formal-languages><approximation-algorithms><automata-theory><counting-complexity>
Can we approximate the number of words accepted by an NFA?
R B
# Can we approximate the number of words accepted by an NFA?

(Asked by: username_0 on 2014-08-27)

Let $M$ be an acyclic NFA.

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

In a [related question](https://cstheory.stackexchange.com/questions/8200/counting-words-accepted-by-a-regular-grammar), 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 :).

**Tags:** ds.algorithms, fl.formal-languages, approximation-algorithms, automata-theory, counting-complexity

> **Comments:**
> **username_1**: The word "acyclic" doesn't appear in the linked question. Who suggested that computing $|L(M)|$ is #P-hard for an acyclic NFA $M$?  
> **username_0**: @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".  
> **username_0**: @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.  
> **username_1**: I am fine with your use of "suggested", understand that it only makes sense to count something if it is finite, and agree that considering an acyclic state graph is easier.  I just don't see how this questions was suggested from the linked question.  
> **username_2**: 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).  
> **username_2**: Now I noticed that you had already posted the same question on [cs.stackexchange.com](http://cs.stackexchange.com/questions/28484/counting-the-number-of-words-accepted-by-an-acyclic-nfa) 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.  

---

## 2 answers

### Answer by username_4 on 2021-11-08. Score: 13 | Accepted answer

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

The result was published this year on STOC, by Arenas, Croquevielle, Jayaram and Riveros.

Here is the talk
<https://youtu.be/tyK-uujHMLU>
and the paper
<https://arxiv.org/abs/1906.09226>


---

### Answer by username_3 on 2024-05-11. Score: 5

And now there is a faster FPRAS: <https://arxiv.org/abs/2312.13320>


---

