219 views

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$
1. All of the above
2. (i) only
3. (i) and (ii)  only
4. (ii) and (iii) only

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

### 1 comment

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

1
578 views