789 views
A grammar $G$ is in Chomsky-Normal Form (CNF) if all its productions are of the form $A \to BC$ or $A \to a$, where $A,B$ and $C$, are non-terminals and $a$ is a terminal. Suppose $G$ is a CFG in CNF and $w$ is a string in $L(G)$ of length $n$, then how long is a derivation of $w$ in $G$?

Its answer is $2n-1$ for $n$ length string, because in CNF at every step only $1$ terminal can replace a variable, for example
$S-AB$
$A-a$
$B-c$

For generating string '$ac$' $3$ productions will be used.

Reference :- Peter Linz
edited
0
why 2n-1 ,why not n+1?

can anyone give more examples on this.

what if, if we want to have "aac".
0
please check if this is correct!

S->AB|a

A->CA|a

B->DB|c

C->a

D->c

now if i want to have "aacc"

then

S->AB

->CAB

->aAB

->aaB

->aacB

->aacc

since 7 reductions for 4 length string therefore 2n-1.

Is it correct?
2n-1