## 4 Answers

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$

### 17 Comments

@Arjun @Rajarshi_Sarkar SIR

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

- What is First Form Productions ?
- What is ' k ' Here ?
- Please answer this with an example

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

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

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 ]

### 3 Comments

**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

**For CNF, it is
2l - 1
For GNF, it is
l**

ref CNF : https://www.javatpoint.com/automata-chomskys-normal-form

ref GNF : https://www.javatpoint.com/automata-greibach-normal-form