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

<p>Consider a degenerate case, when you have such a CFG:</p>

<p>$S\rightarrow aA$</p>

<p>$A\rightarrow B$</p>

<p>$B\rightarrow A$</p>

<p>$A\rightarrow aS$</p>

<p>$S\rightarrow a$</p>

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

<p>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$.</p>

CC BY-SA 3.0
2018-01-19T21:54:17.717Z
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.
Michael Wehar
CC BY-SA 3.0
2018-01-19T21:56:28.063Z
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.
Michael Wehar
CC BY-SA 3.0
2018-01-19T20:39:41.207Z
2018-01-19T20:39:41.207Z
Andrey Lebedev
<p><strong>A Counting Problem</strong></p>

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

<p><strong>An Example Instance</strong></p>

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

<p>$S \rightarrow aS$</p>

<p>$S \rightarrow aSb$</p>

<p>$S \rightarrow \epsilon$</p>

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

<p>(1) $S \rightarrow aS \rightarrow aaS \rightarrow aaaSb \rightarrow aaab$</p>

<p>(2) $S \rightarrow aS \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$</p>

<p>(3) $S \rightarrow aSb \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$</p>

<blockquote>
  <p><strong>Question</strong></p>
  
  <p>What is the complexity of this counting problem?  Is it hard for any
  notable counting complexity classes?</p>
</blockquote>

<p><strong>Edit:</strong> 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.</p>

CC BY-SA 3.0
2018-01-19T07:45:06.040Z
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...
holf
CC BY-SA 3.0
2018-01-19T08:28:06.400Z
@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.
Michael Wehar
CC BY-SA 3.0
2018-01-19T08:46:29.393Z
@holf Also, I think your idea with using a modification of CYK is great as well!  I think it works for grammars in Chomsky normal form.  :)
Michael Wehar
CC BY-SA 3.0
2018-01-19T09:49:00.040Z
@holf After thinking more, I suspect that the CYK approach generalizes so that we can solve the counting problem for a string of length $n$ and a cfg of size $n$ with at most $k$ non-terminals per rule in $n^{O(k)}$ time.  It would follow that this parameterized version of the problem is in counting XP.
Michael Wehar
CC BY-SA 3.0
2018-01-20T07:32:47.647Z
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$?
MRC
CC BY-SA 3.0
2018-01-20T15:31:46.133Z
@MRC This is great!  Thank you very much!  I didn't know about WCFG's.  Do you have any references on this problem or know of anywhere I can learn more about weighted CFG's?
Michael Wehar
CC BY-SA 3.0
2018-01-20T15:50:27.583Z
@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: https://arxiv.org/pdf/cmp-lg/9805007.pdf
Some other resources: http://www.cs.toronto.edu/~tfowler/Fowler-Mol2011.pdf
http://vspvijay.com/ptscfg.pdf

Anyway, the CYK algorithm should work fine by just changing how each cell is calculated slightly.
MRC
CC BY-SA 3.0
2018-01-20T16:15:35.840Z
@MRC Thank you so much!!  I started reading through.  So can we beat $n^{O(k)}$ time where $k$ is an upper bound for the number of non-terminals on the right side of each rule?
Michael Wehar
CC BY-SA 3.0
2018-01-23T08:51:21.443Z
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']$ .
holf
CC BY-SA 3.0
2018-01-23T18:02:00.170Z
@holf Thank you very much!!  I believe that this works now.  :)
Michael Wehar
CC BY-SA 3.0
2018-01-23T18:31:08.927Z
@MRC With Holf's comment, I now am fairly convinced that we can modify the grammar and apply a variation on CYK to achieve a polynomial time algorithm.  Thank you so much for all of your help!!  :)
Michael Wehar
<cc.complexity-theory><fl.formal-languages><counting-complexity><grammars><context-free>
What is the complexity of counting parse trees?
Michael Wehar
# What is the complexity of counting parse trees?

(Asked by: username_0 on 2018-01-19)

**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$

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

**Tags:** cc.complexity-theory, fl.formal-languages, counting-complexity, grammars, context-free
> **Comments:**
> **username_1**: 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...  
> **username_0**: @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.  
> **username_0**: @holf Also, I think your idea with using a modification of CYK is great as well!  I think it works for grammars in Chomsky normal form.  :)  
> **username_0**: @holf After thinking more, I suspect that the CYK approach generalizes so that we can solve the counting problem for a string of length $n$ and a cfg of size $n$ with at most $k$ non-terminals per rule in $n^{O(k)}$ time.  It would follow that this parameterized version of the problem is in counting XP.  
> **username_2**: 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$?  
> **username_0**: @MRC This is great!  Thank you very much!  I didn't know about WCFG's.  Do you have any references on this problem or know of anywhere I can learn more about weighted CFG's?  
> **username_2**: @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: https://arxiv.org/pdf/cmp-lg/9805007.pdf Some other resources: http://www.cs.toronto.edu/~tfowler/Fowler-Mol2011.pdf http://vspvijay.com/ptscfg.pdf  Anyway, the CYK algorithm should work fine by just changing how each cell is calculated slightly.  
> **username_0**: @MRC Thank you so much!!  I started reading through.  So can we beat $n^{O(k)}$ time where $k$ is an upper bound for the number of non-terminals on the right side of each rule?  
> **username_1**: 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']$ .  
> **username_0**: @holf Thank you very much!!  I believe that this works now.  :)  
> **username_0**: @MRC With Holf's comment, I now am fairly convinced that we can modify the grammar and apply a variation on CYK to achieve a polynomial time algorithm.  Thank you so much for all of your help!!  :)  

---

## 1 answers

### Answer by username_3 on 2018-01-19. Score: 2

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

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  

---

