The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
879 views
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form?

(a). $2l$

(b). $2l +1$

(c). $2l -1$

(d). $l$
asked in Theory of Computation by Veteran (68.8k points)
retagged by | 879 views

3 Answers

+18 votes
Best answer
Chomsky Normal Form (If all of its production rules are of the form):
A -> BC or
A -> a or
S -> $\varepsilon$

where A, B and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and $\varepsilon$ is the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if $\varepsilon$ is in L(G), namely, the language produced by the context-free grammar G.

Applying productions of the first form will increase the number of nonterminals from $k$ to $k + 1$, since you replace one nonterminal (-1) with two nonterminals (+2) for a net gain of +1 nonterminal. Since you start with one nonterminal, this means you need to do $l - 1$ productions of the first form. You then need $l$ more of the second form to convert the nonterminals to terminals, giving a total of $l + (l - 1) = 2l - 1$ productions.
answered by Veteran (35.8k points)
selected by
In CNF, any non-terminal can derive empty string?
Corrected.

not getting last paragraph? frown

@Arjun @Rajarshi_Sarkar SIR

Applying productions of the first form will increase the number of nonterminals from k to k + 1, 

  1.  What is First Form Productions ?
  2. What is ' k ' Here  ?
  3. Please answer this with an example 
@arjun sir , is $\epsilon$ production in CNF ?
Wikipedia says so- but only for start symbol. You can check in your TOC book too.

@arjun sir ,
I used to follow Mishra . It was easy to understand . And in my classnotes it is written does not have epsilon production

From spinser .
 

If only A -> BC and A -> a is there, i.e the language does not include empty string, then it is CRF (chomsky reduced form).

@Arjun @Kapil  @pC SIR could u explain my doubt ? I too wanted to take part in the discussion :(

Applying productions of the first form will increase the number of nonterminals from k to k+1, since you replace one nonterminal (-1) with two nonterminals (+2) for a net gain of +1 nonterminal. Since you start with one nonterminal, this means you need to do l−1 productions of the first form. You then need llmore of the second form to convert the nonterminals to terminals, giving a total of l+(l−1)=2l−1productions.

Now  I understand that , 
first form  A->BC  and second form : A->a

Let given grammer  ( as expained in below answer by @pC ) 
S→AB

A→BC|a

B→CC|b

and input string be :w = ab 

 Could u explain the last paragraph ?? Like 

  • How  the non terminals gets increased ?
  • does k denote |w|  ?
$S \to AB \\ \to aB \\ \to ab$.

So, derivation length is 3 for $|w|=2$.

Say if $S\to AB \\ \to ACC $

Now, the non-terminal got increased.
$k$ denote the no. of non-terminals at any step.

Arjun SIR, Not understood  S -> ACC  . This part .Why do we need to go with that production (B->CC ) ?
Not able to follow that last paragraph :(

That is needed for the string "abb" rt? When we chose a production of the form $X \to YZ$, no. of non-terminals increase by 1 and when it is $X \to p$ where $p$ is a terminal, no. of non-terminals decrease by 1. And for a derivation, finally, no. of non-terminals should be 0.
Thank you so much for cearling my silly doubt
Impeccable explanation.. Thanks
+4 votes

Chomsky Normal Form (If all of its production rules are of the form)

'

 

Source : Spinser 

According to Question :
Assuming the grammer (given ) is in CNF and we need to find the length of the production .

Consider a Grammer in CNF Form
$S\rightarrow AB$

$A\rightarrow BC | a $

$B\rightarrow CC| b $

Derivation w = ab  $|w|= n=2$

$S\rightarrow AB$

$S\rightarrow aB$

$S\rightarrow ab$

We took 3 derivations .

When $n=2$ Number of productions in derivation is 3 . From options  $2n-1$ satisfying this . Hence option c

[ need @arjun Sir , to verify this ]

answered by Veteran (23.9k points)
edited by
yes, bit how can we be sure that length cannot be larger for someother string?

That need a mathematical approach . It is best described here  on Problem 2.26

Yes, but in this question you cannot simply substitute the choice- because the question asks for "how long can a derivation be" which is like "maximum length of derivation". So, if you substitute the highest value choice and get "yes", then fine. Other values cannot be substituted- because we never know if they can happen for some other string.
+3 votes

A CFG is in Chomsky normal form when every rule is of the form A → BC and A → a, where a is a terminal, and A, B, and C are variables. Further B and C are not the start variable. Additionally we permit the rule S → ε where S is the start variable.

if G is a context-free grammar in Chomsky normal form, and w is a string of length n ≥ 1, then any leftmost derivation of w from any variable X contains exactly 2n − 1 steps. 

https://courses.cs.washington.edu/courses/cse322/08au/lec14.pdf

https://courses.engr.illinois.edu/cs373/sp2009/lectures/old/lect_15.pdf

answered by Boss (7.5k points)


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

32,330 questions
39,146 answers
108,247 comments
36,501 users