in Theory of Computation edited by
219 views
3 votes
3 votes

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
in Theory of Computation edited by
by
219 views

1 Answer

5 votes
5 votes
Best answer

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

selected by

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

0
0
Answer:

Related questions