Question

Which of the following grammars are in Chomsky Normal Form:

(a) S->AB|BC|CD, A->0, B->1, C->2, D->3

(b) S->AB, S->BCA|0|1|2|3

(c) S->ABa, A->aab, B->Ac

(d) All of the mentioned

This question was addressed to me in a job interview.

This intriguing question comes from Chomsky Normal Form topic in division Properties of Context Free Languages of Automata Theory

Answer 1

The correct answer is (a) S->AB|BC|CD, A->0, B->1, C->2, D->3

Easiest explanation: We can eliminate the options on the basis of the format we are aware of: A->BC, B->b and so on.