5
$\begingroup$

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?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.