Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
