Parse tree

Question

Consider the following grammar

$S \rightarrow SS/Sa/aS/a$

Construct Parse Tree for $w=aaaa$ as many as possible? How many parse trees are possible?

Comments

20 ?

Answer 1

Let f(n) be the number of ways to generate aⁿ. We have,

f(n) = $2*f(n-1)$  <-- due to the rule  S -> aS|Sa
       + $\sum_{i=1}^{n-1} f(i)*f(n-i)$ < --- due to the rule S -> SS

So, $f(n) = 2f(n-1)+\sum_{k=1}^{n-1} f(k)*f(n-k)$ with f(1) = 1

$\therefore f(2)=2f(1)+f(1)^2 = 3 \\ f(3) = 2f(2)+f(1)*f(2)+f(2)*f(1) = 12 \\ f(4) = 2f(3)+f(1)*f(3)+f(2)^2+f(3)*f(1) = 57$

Comments

f(n) = 2∗f(n−1)  <-- due to the rule  S -> aS|Sa
       + ∑n−1i=1f(i)∗f(n−i) < --- due to the rule S -> SS
 

How you came up with this part? Explain your thought process a little bit.