GateAI
Context-Free Grammars and PDAs

GATE CSE 2016 Set 2 · Q43

MCQ2 marksEasy

Time

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

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) L1 is context-free while L2 is not context-free.

Context-Free Grammars and PDAs

Let us analyze both languages:

  1. Language L1={anbmcn+m:m,n≥1}L_1 = \{a^n b^m c^{n+m} : m, n \ge 1\}:

    • The number of cc's equals the sum of the number of aa's and bb's (∣c∣=∣a∣+∣b∣|c| = |a| + |b|).

    • A Pushdown Automaton (PDA) can push all incoming aa's and bb's onto the stack and pop one symbol from the stack for each matching cc.

    • A Context-Free Grammar (CFG) generating L1L_1 can be written as:

      S→aSc∣aAcS \rightarrow aSc \mid aAc
      A→bAc∣bcA \rightarrow bAc \mid bc
    • Therefore, L1L_1 is a context-free language.

  2. Language L2={anbnc2n:n≥1}L_2 = \{a^n b^n c^{2n} : n \ge 1\}:

    • A single stack PDA cannot simultaneously verify that the number of aa's equals the number of bb's and that the number of cc's equals 2n2n.

    • Using the Pumping Lemma for CFLs, one can show that pumping will disrupt either the count equality of aa's and bb's or the proportion of cc's.

    • Therefore, L2L_2 is not context-free.

Thus, L1L_1 is context-free while L2L_2 is not context-free.

Therefore, the correct option is (B).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Context-Free Grammars and PDAs previous year question is Q43 of the GATE CSE 2016 Set 2 paper. Find more GATE CSE PYQs on Context-Free Grammars and PDAs in Theory of Computation, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Context-Free Grammars and PDAs PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Context-Free Grammars and PDAs in GATE CSE

Context-Free Grammars and PDAs has 26 GATE CSE PYQs across 17 papers from 2011 to 2026. 9 of them are 2-mark MCQs like this one, and GATE CSE 2016 Set 2 has 2.

How GATE tests Context-Free Grammars and PDAs

More from GATE CSE 2016 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2016 Set 2 · Q43 · MCQ

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?

Topic-wise GATE CS PYQs with verified steps

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