Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
There happened to be a following question -
In any Chomsky Normal Form grammar $G$, how many nodes will all parse trees for terminal strings of length $n>0$ generated by G have?
I tried for some examples & arrived at the answer $2^{n}+1$ but it is incorrect & obviously trying examples is not a sophisticated way. The correct answer given is $3^{n}-1.$ Can anyone explain how this answer comes?
Both of the answers are wrong. To find the correct answer, let us consider the grammar $$ S \to SA \mid a \\ A \to a $$
You can check that the tree corresponding to $S \to a$ has 2 nodes, the one corresponding to $S \to SA \to aA \to aa$ has 5 nodes, and the one corresponding to $S \to SA \to SAA \to aAA \to aaA \to aaa$ has 8 nodes. This corresponds to the formula $3n-1$ (rather than $3^n-1$, the formula you quoted).
Let us now prove that this formula is correct. The proof is by induction, where we allow varying the starting nonterminal. When $n = 1$, the derivation must be of the form $A \to \sigma$, which includes 2 nodes. When $n > 1$, the first step must be $A \to BC$, where $B$ gives rise to a word of length $k$, and $C$ gives rise to a word of length $n-k$. The entire tree is formed from the trees corresponding to $B,C$ by adding the root, and so the total number of nodes is $$1 + (3k-1) + (3(n-k)-1) = 3n-1.$$
