The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
969 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$?
asked in Compiler Design by Veteran (59.8k points) | 969 views

4 Answers

+24 votes
Best answer
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
answered by Boss (42.1k points)
edited by
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

->aaDB

->aacB

->aacc

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

Is it correct?
0

@Gate Fever yes it is correct 

0 votes
2n-1
answered by Active (2.1k points)
0 votes
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.
answered by Active (1.3k points)
0

@Radha mohan

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!
0 votes
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.
answered by Active (1.1k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

46,762 questions
51,219 answers
176,461 comments
66,579 users