91Ó°ÊÓ

A context-free grammar$G$, is said to be in Chomsky normal formif all of its production rules are of the form

$$\begin{gathered} A→BC,or \\ A→a, \end{gathered}$$

First note that in rules of the form $A→BC$, neither $B$nor $C$can be$S$

This means that in a derivation of a string w of length greater than zero, the rule$S→\mathrm{Î\mu },$

if it exists in$G$cannot be used, so the derivation can use only rules of the forms,

$$\begin{gathered} A→BC,or \\ A→a, \end{gathered}$$

Each application of a rule of the first form lengthens the string derived by one symbol.

Since the $A→$rules leave the length of the string the same, this means that $A→B\mathrm{C}$rules are used exactly $n-1$times in deriving a string w of length n.

Since each use of a rule $A→$an introduces one terminal and this terminal can never be removed, rules of the form$A→a$are used exactly n times in the derivation of string w consisting of n terminals. In total, the derivation of w has length

$n-1+n=$$2n-1$.

The first step is that if$A$is a variable of$G$different from $S$, then it is impossible to derive ε from $A$.

Here show the following more general statement: if $A$is a variable and w is a string of terminals of length $nâ\copyright ¾1$, then any derivation of w from $A$in $G$takes $2n-1$steps.

The proof is by induction on n. If $n=1$, then w is a single terminal. If the derivation of w from A began with the rule $A→BC$, then, since neither$B$nor$C$is$S$and$A→a$would have length at least two.

Thus, the derivation must consist of a single application of the rule$A→c$and so has length one.

Since, $2×1-1=1$, the desired relationship holds in this case.

Now, suppose that $n>1$and the result holds for strings of length $j$with $1â\copyright ½jâ\copyright ½n-1$.

If w is a string of terminals of length n that can be derived from $A$, then the derivation must begin with a rule $A→B\mathrm{C}$.

Let $x=yz$, where $y$is the part of $x$derived from $B$and $z$is the part derived from $C$. Since neither $B$nor $C$is $S$neither $y$nor $z$is ε.

Thus, apply the inductive hypothesis to both$y$ and $z$. This means that if

$$\begin{gathered} \left|y\right|=kand \\ \left|z\right|=n-k, \end{gathered}$$

Then the derivation of y from $B$takes$2k-1$ steps and the derivation of $z$from $C$takes$2\left(n-k\right)-1$ steps.

The total length of the derivation of w from$A$ is then

$1+\left(2k-1\right)+\left(2\left(n-k\right)-1\right)=$$2n-1$

which completes the induction.

Hence, it isproved that if$G$ is a context-free grammar in Chomsky normal form, then for any string $w∈L\left(G\right)$of length$nâ\copyright ¾1$,exactly$2n-1$steps are required for any derivation of $w$.