Question

Which among the following is a CFG for the given Language:

(a) L={x∈{0,1}*|number of zeroes in x=number of one’s in x}

(b) S->e|0S1|1S0|SS

(c) S->0B|1A|e  A->0S  B->1S

(d) All of the mentioned

The question was asked during an online interview.

This is a very interesting question from Sentential Forms topic in portion Context Free Grammars and Languages of Automata Theory

Answer 1

Correct choice is (c) S->0B|1A|e  A->0S  B->1S

Explanation: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.