GateAI
Context-Free Grammars and PDAs

GATE CSE 2015 Set 3 · Q32

MCQ2 marksMedium

Time

Which of the following languages are context-free? L1={ambnanbm∣m,n≥1}L_1 = \{a^m b^n a^n b^m \mid m, n \ge 1\} L2={ambnambn∣m,n≥1}L_2 = \{a^m b^n a^m b^n \mid m, n \ge 1\} L3={ambn∣m=2n+1}L_3 = \{a^m b^n \mid m = 2n + 1\}

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) L1 and L3 only

Context-Free Grammars and PDAs
  1. Language L1={ambnanbm∣m,n≥1}L_1 = \{a^m b^n a^n b^m \mid m, n \ge 1\}: The dependencies in L1L_1 are nested in a LIFO manner (the inner bnanb^n a^n can be matched first, and the outer ambma^m b^m is matched afterward). A pushdown automaton (PDA) can push all initial aa's onto the stack, then push all bb's, pop a bb for each subsequent aa to match bnanb^n a^n, and finally pop an aa for each trailing bb to match ambma^m b^m. Because a single stack suffices, L1L_1 is context-free.

  2. Language L2={ambnambn∣m,n≥1}L_2 = \{a^m b^n a^m b^n \mid m, n \ge 1\}: The dependencies in L2L_2 are cross-serial (the first block of aa's matches the second block of aa's, and the first block of bb's matches the second block of bb's). A single stack cannot maintain and verify both counts simultaneously. By the Pumping Lemma for Context-Free Languages, L2L_2 is not context-free.

  3. Language L3={ambn∣m=2n+1}L_3 = \{a^m b^n \mid m = 2n + 1\}: L3={a2n+1bn∣n≥0}L_3 = \{a^{2n+1} b^n \mid n \ge 0\}. A PDA can easily match one bb for every two aa's popped from the stack (ignoring the single extra leading aa). Thus, L3L_3 is context-free (generated by S→aS′bS \to aS^{\prime}b, S′→aaS′b∣aS^{\prime} \to aaS^{\prime}b \mid a).

Therefore, only L1L_1 and L3L_3 are context-free, which matches option (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 Q32 of the GATE CSE 2015 Set 3 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 it is the only one in GATE CSE 2015 Set 3.

How GATE tests Context-Free Grammars and PDAs

More from GATE CSE 2015 Set 3

Share this solution

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

GateAI solution cardGATE CSE 2015 Set 3 · Q32 · MCQ

Which of the following languages are context-free? L1 = {am bn an bm m, n ≥ 1} L2 = {am bn am bn m, n ≥ 1} L3 = {am bn m = 2n + 1}

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.