1.1k 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?
0

@Gate Fever yes it is correct

2n-1
firstly we have to make the required lengh which requires exactly 2n-1 productions becuase we initiallly start with 1 symbol after that convert each variable to terminal using n more productions thus total productions required is n+n-1=2n-1.
0

pls chk my above comment in which "aacc" is derived!

pls chk if it is correct or not

0
ya for that instance it is fine
0
ok, that means the grammar is correct!

actually i was having doubt in the grammar only,i just wanted to know whether i have written it correctly or not!
Let $w=a_1a_2...a_n$... Let's reverse engineer the string.

Each $a_i$ would have converted using $A \rightarrow a$ from a variable adds to $n$ derivation. Further, those variables $V_1V_2...V_n$ would have derived either rightly or leftly using $A \rightarrow BC$ adds to $n-1$ derivation.