Test by Bikram | Theory of Computation | Test 1 | Question: 3

Question

Which of the following grammars violate the Chomsky Normal Form?

1. $S \rightarrow AB$, $A \rightarrow a , B \rightarrow \epsilon \mid b$
2. $S \rightarrow AcB, A \rightarrow a, B \rightarrow b$
3. $S \rightarrow AB, \ A \rightarrow a, \ B \rightarrow b$

• A. All of the above
• B. (i) only
• C. (i) and (ii)  only
• D. (ii) and (iii) only

Answer 1

CNF: V->VV         V->t    where V is single variable and t is single terminal
1) CNF doesn't contain epsilon
2) S--> AcB  not in the form of V->VV
3) CNF

Comments

CNF do contain epsilon if epsilon is there in language.

We will include epsilon in only start production to make sure we get epsilon in language.

https://cs.stackexchange.com/questions/24012/chomsky-normal-form-epsilon-rule