1.7k 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?

1. $2l$
2. $2l +1$
3. $2l -1$
4. $l$
edited | 1.7k views

Chomsky Normal Form (If all of its production rules are of the form):
$A \rightarrow BC$ or
$A \rightarrow a$ or
$S \rightarrow \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.
edited by
+2
In CNF, any non-terminal can derive empty string?
+1
Corrected.
+2

not getting last paragraph?

0

@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  ?
0
@arjun sir , is $\epsilon$ production in CNF ?
0
Wikipedia says so- but only for start symbol. You can check in your TOC book too.
+2

@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 .

+7
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).
0

@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|  ?
+2
$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.
0

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 :(

+2
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.
0
Thank you so much for cearling my silly doubt
0
Impeccable explanation.. Thanks
0
Since the given grammar is in CNF for every single terminal symbol we have a corresponding non terminal so from the first production of starting symbol we get two terminals ( eg $S->AB$). Since every non terminal produces only one non terminal we need that much amount of non terminals but here from the start symbol we get two non terminals (that's the reason of $l-1$) and for every terminal derivation we need additional $l$ steps.

So total $(l-1)+l$ steps.

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 ]

edited by
0
yes, bit how can we be sure that length cannot be larger for someother string?
+1

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

+1
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.

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

1
2