# Counting words of length $n$ in an inherently ambiguous CFG?

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?

## 1 Answer

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

• ok I'll delete my comment (and this one shortly) since it no longer applies. – Neal Young Jul 5 '20 at 16:35