<p>It seems that this problem is NP-hard, if both the grammar and <span class="math-container">$n$</span> (in unary notation) are considered to be parts of the input.</p>
<p>There is a classical construction that is used to show that universality of a CFG is undecidable. The construction takes a Turing machine <span class="math-container">$M$</span> and outputs a grammar <span class="math-container">$G_M$</span>, such that all strings in <span class="math-container">$L(G_M)$</span> <em>are not valid accepting computations of <span class="math-container">$M$</span></em> in some encoding.
Sections 1 and 3 of <a href="https://liacs.leidenuniv.nl/%7Ehoogeboomhj/second/codingcomputations.pdf" rel="nofollow noreferrer">this overview</a> do a decent job of explaining the main ideas, though they skip over a lot of details (how to deal with tape extensions, e.t.c.).</p>
<p>Said construction should work for non-deterministic Turing machines as well (the construction does not use determinism anywhere, I think). Now, consider a polynomial time non-deterministic Turing machine <span class="math-container">$M$</span> that solves SAT by guessing a satisfying assignment. Construct a grammar <span class="math-container">$G_M$</span> that corresponds to <span class="math-container">$M$</span>.</p>
<p>I claim that a polynomial time algorithm to compute the number of strings in <span class="math-container">$G_M$</span> with a given length yields a polynomial time algorithm for solving SAT. Indeed, consider a given SAT-formula <span class="math-container">$\varphi$</span>, it corresponds to some initial configuration <span class="math-container">$x_\varphi$</span> of <span class="math-container">$M$</span>. Then, the language <span class="math-container">$L' = L(G_M) \cup \overline{(x_\varphi\#)(\Gamma \cup Q \cup \{\#\})^*}$</span> is the language of all strings that are either not valid accepting computations of <span class="math-container">$M$</span> <em>or</em> valid accepting computations of <span class="math-container">$M$</span> that do not start in configuration <span class="math-container">$x_\varphi$</span>.</p>
<p>Hence, if <span class="math-container">$\varphi$</span> is satisfiable, there is a string of polynomial length from <span class="math-container">$(\Gamma \cup Q \cup \{\#\})^*$</span> that does not belong to <span class="math-container">$L'$</span>. This string correspond to <span class="math-container">$M$</span> guessing some satisfying assignment correctly. On the other hand, for unsatisfiable <span class="math-container">$\varphi$</span>, there are no accepting computations of <span class="math-container">$M$</span>, hence there will be no short strings (or any strings, really) that <em>do not</em> belong to <span class="math-container">$L'$</span>.</p>
<p>The last thing to note is that <span class="math-container">$L'$</span> is a union of a CFL <span class="math-container">$L(G_M)$</span> and a regular language <span class="math-container">$\overline{(x_\varphi\#)(\Gamma \cup Q \cup \{\#\})^*}$</span>. Therefore, it is recognised by a grammar <span class="math-container">$G_M'$</span> of size <span class="math-container">$|G_M| + O(|\varphi|)$</span>. Hence, computing the number of strings with a given length in <span class="math-container">$G_M'$</span> is NP-hard, because SAT can be reduced to this problem.</p>
<p><strong>UPD.</strong> In fact, this problem is #P-complete, because every satisfying assignment of <span class="math-container">$\varphi$</span> corresponds to exactly one short string not in <span class="math-container">$L'$</span>, yielding a reduction from #SAT.</p>

CC BY-SA 4.0
2020-07-05T16:35:56.867Z
ok I'll delete my comment (and this one shortly) since it no longer applies.
Neal Young
CC BY-SA 4.0
2020-07-05T12:50:17.310Z
2020-07-05T17:58:02.567Z
2020-07-05T17:58:02.567Z
Kaban-5
<p>There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, the algorithm only computes the number of parse trees resulting in strings of length $n$. Therefore, this result is not the number of words of length $n$ in an ambiguous CFG.</p>

<p>Is there a result (other than testing all possible strings of length $n$) for inherently ambiguous CFGs?</p>

<grammars><context-free><dynamic-programming>
Counting words of length $n$ in an inherently ambiguous CFG?
Ryan Dougherty
# Counting words of length $n$ in an inherently ambiguous CFG?

(Asked by: username_0 on 2015-10-07)

There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, the algorithm only computes the number of parse trees resulting in strings of length $n$. Therefore, this result is not the number of words of length $n$ in an ambiguous CFG.

Is there a result (other than testing all possible strings of length $n$) for inherently ambiguous CFGs?

**Tags:** grammars, context-free, dynamic-programming

---

## 1 answers

### Answer by username_1 on 2020-07-05. Score: 2

It seems that this problem is NP-hard, if both the grammar and $n$ (in unary notation) are considered to be parts of the input.

There is a classical construction that is used to show that universality of a CFG is undecidable. The construction takes a Turing machine $M$ and outputs a grammar $G\_M$, such that all strings in $L(G\_M)$ *are not valid accepting computations of $M$* in some encoding.
Sections 1 and 3 of [this overview](https://liacs.leidenuniv.nl/%7Ehoogeboomhj/second/codingcomputations.pdf) do a decent job of explaining the main ideas, though they skip over a lot of details (how to deal with tape extensions, e.t.c.).

Said construction should work for non-deterministic Turing machines as well (the construction does not use determinism anywhere, I think). Now, consider a polynomial time non-deterministic Turing machine $M$ that solves SAT by guessing a satisfying assignment. Construct a grammar $G\_M$ that corresponds to $M$.

I claim that a polynomial time algorithm to compute the number of strings in $G\_M$ with a given length yields a polynomial time algorithm for solving SAT. Indeed, consider a given SAT-formula $\varphi$, it corresponds to some initial configuration $x\_\varphi$ of $M$. Then, the language $L' = L(G\_M) \cup \overline{(x\_\varphi\#)(\Gamma \cup Q \cup \{\#\})^\*}$ is the language of all strings that are either not valid accepting computations of $M$ *or* valid accepting computations of $M$ that do not start in configuration $x\_\varphi$.

Hence, if $\varphi$ is satisfiable, there is a string of polynomial length from $(\Gamma \cup Q \cup \{\#\})^\*$ that does not belong to $L'$. This string correspond to $M$ guessing some satisfying assignment correctly. On the other hand, for unsatisfiable $\varphi$, there are no accepting computations of $M$, hence there will be no short strings (or any strings, really) that *do not* belong to $L'$.

The last thing to note is that $L'$ is a union of a CFL $L(G\_M)$ and a regular language $\overline{(x\_\varphi\#)(\Gamma \cup Q \cup \{\#\})^\*}$. Therefore, it is recognised by a grammar $G\_M'$ of size $|G\_M| + O(|\varphi|)$. Hence, computing the number of strings with a given length in $G\_M'$ is NP-hard, because SAT can be reduced to this problem.

**UPD.** In fact, this problem is #P-complete, because every satisfying assignment of $\varphi$ corresponds to exactly one short string not in $L'$, yielding a reduction from #SAT.

> **Comments:**
> **username_2**: ok I'll delete my comment (and this one shortly) since it no longer applies.  

---

