Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)

Question

Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$

Answer 1

Formally, we can prove by Induction , but let me give you an intuitive idea.
There are two types of derivations , one which is of the form A$\rightarrow$TD and A$\rightarrow$b.

To generate a string of length we need n-1 derivations of the form A$\rightarrow$TD. And to finally replace the non-terminals , we need n productions of the form A$\rightarrow$b to replace each non-terminal to a terminal.

 Hence, we need n-1+n=2n-1 productions in all exactly , to get a string of length n.