2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.