Question

If G is a context-free grammar and w is a string of length n in L(G), how long is a derivation of w in G, if G is in Chomsky normal form?

Answer 1

A context-free grammar G is Chomsky normal form if all productions are in one of two simple form, either:
1. A→ BC where A,B and C are variables,or
2. A→ a where A is a variable and a is terminal.
So, for any string of length n first prodcution of type A→BC is used n-1 times to produce sentential form of length n containing only variables and then each variable is replaced by a terminal using productions of type A→a, n times.
So the length of derivation to generate a string w of length n in CNF is n+n-1 = 2n-1.
Example :
S $\to$ XY
Y $\to$ XZ
X $\to$ a
Z $\to$ b
Toderive the string "aab" by using above CNF
S $\to$ XY
$\Rightarrow$ aY
$\Rightarrow$ zXZ
$\Rightarrow$aaZ
$\Rightarrow$aab
It requires 5 steps
$2\ast |aab|-1=2\times 3-1=5$