GATE | GATE-CS-2016 (Set 1) | Question 52

Consider the following context-free grammars:

Which one of the following pairs of languages is generated by G1 and G2, respectively


(A) A
(B) B
(C) C
(D) D

Answer: (D)

Explanation: In G1, there will be atleast 1 b becase S->B and B->b. But no of A’s can be 0 as well and no of A and B are independent.

In G2, either we can take S->aA or S->bB. So it must have atleast 1 a or 1 b.

So option D is correct.

Leave a Reply

Your email address will not be published. Required fields are marked *