GATE CSE 1994 | Question: 20

Question

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$?

Comments

For GNF it is n.

Answer 1

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\to AB$
• $A \to a$
• $B \to c$

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

Reference:- Peter Linz

Comments

why 2n-1 ,why not n+1?

can anyone give more examples on this.

what if, if we want to have "aac".

---

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

->aaDB

->aacB

->aacc

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

Is it correct?

---

@Gate Fever yes it is correct 

Answer 2

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.

Answer 3

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.

Comments

@Radha mohan

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

pls chk if it is correct or not

---

ya for that instance it is fine

---

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!