The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
867 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.6k points) | 867 views

3 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 (41k 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 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 ago by Active (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

42,598 questions
48,599 answers
155,644 comments
63,710 users