Skip to content
GATEiit

GATE CSE 2025 Session 1 Q45: Context-freeness of a^m b^m c^(m+n) and a^m b^n c^(m+n)

Question

Consider the following two languages over the alphabet {a,b,c}\{a, b, c\}, where mm and nn are natural numbers.

L1={ambmcm+n∣m,n≥1}L_1 = \{a^m b^m c^{m+n} \mid m, n \ge 1\}

L2={ambncm+n∣m,n≥1}L_2 = \{a^m b^n c^{m+n} \mid m, n \ge 1\}

Which ONE of the following statements is CORRECT?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2025 final answer key)

Concept used: A single stack can match nested counts but cannot compare one count against two others.

First step: L2L_2: push for every aa and bb, pop for every cc. L1L_1 requires #a = #b and #c > #a at once, which needs two comparisons (use the pumping lemma).

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 1 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2025 Session 1 questions →