Consider the following languages: L1 = \an bm cn+m : m, n 1\ L2 = \an bn c2n : n 1\ Which one of the following is TRUE? A) Both L1 and L2 are context-free. B) L1 is context-free while L2 is not context-free. C) L2 is context-free while L1 is not context-free. D) Neither L1 nor L2 is context-free.

Official answer: B) L1 is context-free while L2 is not context-free.. Explanation: Let us analyze both languages: 1. Language L1 = \an bm cn+m : m, n 1\: - The number of c's equals the sum of the number of a's and b's (|c| = |a| + |b|). - A Pushdown Automaton (PDA) can push all incoming a's and b's onto the stack and pop one symbol from the stack for each matching c. - A Context-Free Grammar (CFG) generating L1 can be written as: S aSc aAc A bAc bc - Therefore, L1 is a context-free language. 2. Language L2 = \an bn c2n : n 1\: - A single stack PDA cannot simultaneously verify that the number of a's equals the number of b's and that the number of c's equals 2n. - Using the Pumping Lemma for CFLs, one can show that pumping will disrupt either the count equality of a's and b's or the proportion of c's. - Therefore, L2 is not context-free. Thus, L1 is context-free while L2 is not context-free. Therefore, the correct option is (B).

A) Both L1 and L2 are context-free.

B) L1 is context-free while L2 is not context-free.

C) L2 is context-free while L1 is not context-free.

D) Neither L1 nor L2 is context-free.

Theory of Computation · Context-Free Grammars and PDAs

Official IIT answer key · IISc Bangalore · Audited Aug 2026

Take topic test

GATE CSE 2016 Set 2 Q43 · MCQ · 2 marks

Consider the following languages: $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$ $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$ Which one of the following is TRUE?

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 2 Q43 · MCQ · 2 marks

Consider the following languages: $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$ $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$ Which one of the following is TRUE?

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 languages: $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$ $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$ Which one of the following is TRUE?

Step-by-step verified solution

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

More from GATE CSE 2016 Set 2

More on Context-Free Grammars and PDAs

Consider the following languages: $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$ $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$ Which one of the following is TRUE?

Step-by-step verified solution

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

More from GATE CSE 2016 Set 2

More on Context-Free Grammars and PDAs

Consider the following languages: L1={anbmcn+m:m,n≥1}L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}L1​={anbmcn+m:m,n≥1} L2={anbnc2n:n≥1}L_2 = \{a^n b^n c^{2n} : n \ge 1\}L2​={anbnc2n:n≥1} Which one of the following is TRUE?

Step-by-step verified solution

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

More from GATE CSE 2016 Set 2

More on Context-Free Grammars and PDAs

Share this solution

Consider the following languages: L1={anbmcn+m:m,n≥1}L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}L1​={anbmcn+m:m,n≥1} L2={anbnc2n:n≥1}L_2 = \{a^n b^n c^{2n} : n \ge 1\}L2​={anbnc2n:n≥1} Which one of the following is TRUE?

Step-by-step verified solution

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

More from GATE CSE 2016 Set 2

More on Context-Free Grammars and PDAs

Share this solution

Consider the following languages: $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$ $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$ Which one of the following is TRUE?

Consider the following languages: $L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}$ $L_2 = \{a^n b^n c^{2n} : n \ge 1\}$ Which one of the following is TRUE?