retagged by
14,758 views

4 Answers

Best answer
53 votes
53 votes

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.

Correct Answer: $C$

edited by
10 votes
10 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 ]

edited by
7 votes
7 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

Answer:

Related questions

23 votes
23 votes
4 answers
1
Kathleen asked Sep 13, 2014
4,672 views
Context-free languages are:closed under unionclosed under complementationclosed under intersectionclosed under Kleene closure
28 votes
28 votes
1 answer
2
42 votes
42 votes
8 answers
3
Kathleen asked Sep 13, 2014
14,285 views
Which of the following regular expression identities is/are TRUE?$r^{(^\ast)} =r^\ast$$(r^\ast s^\ast)=(r+s)^\ast$$(r+s)^\ast = r^\ast + s^\ast$$r^\ast s^\ast = r^\ast+s^...
24 votes
24 votes
4 answers
4
Kathleen asked Sep 13, 2014
9,915 views
Which of the following is/are a tautology?$a \vee b \to b \wedge c$$a \wedge b \to b \vee c$$a \vee b \to \left(b \to c \right)$$a \to b \to \left(b \to c \right)$