A Counting Problem

Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$?

An Example Instance

Let's consider an example instance consisting of a CFG $G$ with grammar rules:

$S \rightarrow aS$

$S \rightarrow aSb$

$S \rightarrow \epsilon$

And, a string $s = aaab$. Then, there are three parse trees for $s$:

(1) $S \rightarrow aS \rightarrow aaS \rightarrow aaaSb \rightarrow aaab$

(2) $S \rightarrow aS \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$

(3) $S \rightarrow aSb \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$


What is the complexity of this counting problem? Is it hard for any notable counting complexity classes?

Edit: Based on @MRC's comments, it seems that this problem is equivalent to calculating the weight of $s$ relative to the weighted CFG obtained by attaching the semiring $(\mathbb{N}, +, \times)$ to $G$ and assigning the weight of 1 to each of $G$'s rules.

  • 2
    $\begingroup$ I do not have all the algorithms stored in my RAM right now so it is a wild guess but it seems to me that CYK algorithm may be easily generalized to count parse trees. Now you still need a transformation into Chomsky normal form that preserves this number, which may be the main problem... $\endgroup$ – holf Jan 19 '18 at 7:45
  • $\begingroup$ @holf Yes! You made a great observation!! Namely, two grammars that recognizes the same strings might have a different number of parse trees for each string so rewriting the grammar into Chomsky normal form might not work. $\endgroup$ – Michael Wehar Jan 19 '18 at 8:28
  • 2
    $\begingroup$ Is this problem not equivalent to just finding the weight of a word generated by the weighted CFG constructed by attaching the semiring $(\mathbb{N}, +, \times)$ and giving each production rule weight $1$? $\endgroup$ – MRC Jan 20 '18 at 7:32
  • 1
    $\begingroup$ @MichaelWehar Yes, there are some but they are pretty much all about stochastic CFGs since those have had by far the most use in academia. However, most of the algorithms work for general semirings in the same time complexity (disregarding the complexity of $\oplus$ and $\otimes$). A good PhD thesis: arxiv.org/pdf/cmp-lg/9805007.pdf Some other resources: cs.toronto.edu/~tfowler/Fowler-Mol2011.pdf vspvijay.com/ptscfg.pdf Anyway, the CYK algorithm should work fine by just changing how each cell is calculated slightly. $\endgroup$ – MRC Jan 20 '18 at 15:50
  • 1
    $\begingroup$ Doesn't the classical transformation into Chomsky NF ($X \rightarrow X_1 \ldots X_k$ becomes $X \rightarrow X_1A_1$ and $A_i \rightarrow X_{i+1}A_{i+1}$ with $A_i$ symbols fresh per rules in your original grammar) keeps the # of parse trees? If you use a $X \rightarrow X_1A_1$ rule, then you are forced to use the others. Roughly, you count for each $j, l \leq l'$, how many way you have to reduce $X_j \ldots X_k$ to $s[l,l']$ which is in turn the number of way you have to reduce $X_{j}$ to $s[l,l'']$ times the number of way you have to reduce $X_{j+1} \ldots X_k$ to $s[l'',l']$ . $\endgroup$ – holf Jan 23 '18 at 8:51

Because you are asking the question in general, the answer will be: uncertain number of trees.

Consider a degenerate case, when you have such a CFG:

$S\rightarrow aA$

$A\rightarrow B$

$B\rightarrow A$

$A\rightarrow aS$

$S\rightarrow a$

This is a valid grammar, right? Though not normalized. Obviously you can "run" between $A$ and $B$ for any number of times for any given string $s$ generated by this grammar. Each transition between $A$ and $B$ gives you new node in a parse tree, thus we have uncertain number of them.

So, I would rather ask about normalised CFG. For a normalised CFG I guess it should be only one parse tree per the given string $s$.

  • $\begingroup$ This is also a really great point! There could be a sequence of production rules that essentially creates a cycle which would result in infinitely many parse trees for the given string. $\endgroup$ – Michael Wehar Jan 19 '18 at 21:54
  • $\begingroup$ In my opinion, such grammars are valid for the counting problem and we should output infinite (or a designated string such as $\infty$) as the answer. $\endgroup$ – Michael Wehar Jan 19 '18 at 21:56

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.