Consider the following context-free grammars: G1: S aS | B, B b | bB G2: S aA | bB, A aA | B | , B bB | Which one of the following pairs of languages is generated by G1 and G2, respectively? A) \am bn | m > 0 or n > 0\ and \am bn | m > 0 and n > 0\ B) \am bn | m > 0 and n > 0\ and \am bn | m > 0 or n 0\ C) \am bn | m 0 or n > 0\ and \am bn | m > 0 and n > 0\ D) \am bn | m 0 and n > 0\ and \am bn | m > 0 or n > 0\

Official answer: D) \am bn | m 0 and n > 0\ and \am bn | m > 0 or n > 0\. Explanation: Let us analyze the languages generated by each grammar: 1. Grammar G1: - S aS B - B b bB The variable B generates one or more b's: L(B) = b+ = \bn n > 0\. The start variable S generates zero or more a's followed by a string from B: L(G1) = a* b+ = \am bn m 0 and n > 0\. 2. Grammar G2: - S aA bB - A aA B - B bB B generates zero or more b's: L(B) = b*. A generates zero or more a's followed by B: L(A) = a* b*. Then for the start variable S: - Through branch S aA: strings of the form a a* b* = a+ b* = \am bn m > 0 and n 0\. - Through branch S bB: strings of the form b b* = b+ = \a0 bn n > 0\. Taking the union: L(G2) = (a+ b*) (b+) = \am bn m > 0 or n > 0\ (i.e., all strings of the form am bn where at least one of m, n is strictly greater than 0). Matching these gives: - L(G1) = \am bn m 0 and n > 0\ - L(G2) = \am bn m > 0 or n > 0\ This matches option (D).

A) \am bn | m > 0 or n > 0\ and \am bn | m > 0 and n > 0\

B) \am bn | m > 0 and n > 0\ and \am bn | m > 0 or n 0\

C) \am bn | m 0 or n > 0\ and \am bn | m > 0 and n > 0\

D) \am bn | m 0 and n > 0\ and \am bn | m > 0 or n > 0\

Theory of Computation · Context-Free Grammars and PDAs

Official IIT answer key · IISc Bangalore · Audited Aug 2026

Take topic test

GATE CSE 2016 Set 1 Q42 · MCQ · 2 marks

Consider the following context-free grammars: $G_1: S \to aS | B, B \to b | bB$ $G_2: S \to aA | bB, A \to aA | B | \varepsilon, B \to bB | \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ , respectively?

Select an option to check

Key concept

Context-Free Grammars and PDAs

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Context-Free Grammars and PDAs

Context-Free Grammars (CFG) and Pushdown Automata (PDA) form a cornerstone of the GATE CS Theory of Computation syllabus. Questions systematically test the boundary between Regular, DCFL, CFL, and non-CFL classes, structural invariants of grammars (ambiguity, terminal count ratios, derivation steps), and operational tracing of PDAs. Over recent years, the topic has expanded from standard single-choice language classifications to multi-select invariant verification and exact counting NAT questions.

Full Context-Free Grammars and PDAs guide →

More on Context-Free Grammars and PDAs

All 26 questions on Context-Free Grammars and PDAs →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Theory of Computation · Context-Free Grammars and PDAs

Official IIT answer key · IISc Bangalore · Audited Aug 2026

Take topic test

GATE CSE 2016 Set 1 Q42 · MCQ · 2 marks

Consider the following context-free grammars: $G_1: S \to aS | B, B \to b | bB$ $G_2: S \to aA | bB, A \to aA | B | \varepsilon, B \to bB | \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ , respectively?

Select an option to check

Key concept

Context-Free Grammars and PDAs

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Context-Free Grammars and PDAs

Full Context-Free Grammars and PDAs guide →

More on Context-Free Grammars and PDAs

All 26 questions on Context-Free Grammars and PDAs →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Consider the following context-free grammars: $G_1: S \to aS | B, B \to b | bB$ $G_2: S \to aA | bB, A \to aA | B | \varepsilon, B \to bB | \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ , respectively?

Step-by-step verified solution

Check you can still solve Context-Free Grammars and PDAs under a clock

More from GATE CSE 2016 Set 1

More on Context-Free Grammars and PDAs

Consider the following context-free grammars: $G_1: S \to aS | B, B \to b | bB$ $G_2: S \to aA | bB, A \to aA | B | \varepsilon, B \to bB | \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ , respectively?

Step-by-step verified solution

Check you can still solve Context-Free Grammars and PDAs under a clock

More from GATE CSE 2016 Set 1

More on Context-Free Grammars and PDAs

Step-by-step verified solution

Check you can still solve Context-Free Grammars and PDAs under a clock

More from GATE CSE 2016 Set 1

More on Context-Free Grammars and PDAs

Share this solution

Step-by-step verified solution

Check you can still solve Context-Free Grammars and PDAs under a clock

More from GATE CSE 2016 Set 1

More on Context-Free Grammars and PDAs

Share this solution