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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.