The GATE Grind

GATE 2025 CS (CS1) – Question 45

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 2 marks · Multiple choice

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

$L_1 = \{a^m b^m c^{m+n} \mid m,n \ge 1\}$
$L_2 = \{a^m b^n c^{m+n} \mid m,n \ge 1\}$

Which ONE of the following statements is CORRECT?

  1. Both $L_1$ and $L_2$ are context-free languages.
  2. $L_1$ is a context-free language but $L_2$ is not a context-free language.
  3. $L_1$ is not a context-free language but $L_2$ is a context-free language.
  4. Neither $L_1$ nor $L_2$ are context-free languages.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $L_1$ is not a context-free language but $L_2$ is a context-free language.

Explanation

**1. Construct a grammar for L₂.** Use $S\to aSc\mid aTc$ and $T\to bTc\mid bc$. The outer rules produce matching a/c pairs and the inner rules matching b/c pairs, with at least one of each. This generates precisely $a^mb^nc^{m+n}$, so L₂ is context-free.

**2. Choose a pumping-lemma witness for L₁.** Suppose L₁ were context-free with pumping length p. Choose $w=a^pb^pc^{p+1}$. For any permitted decomposition w = uvxyz, the window vxy has length at most p and therefore cannot contain both an a and a c. The pumped parts vy are nonempty.

**3. Check every possible pumping pattern.** If vy changes unequal numbers of a and b, pumping breaks their required equality. If it changes equal positive numbers of both, it changes no c; pumping sufficiently many times makes the a count reach or exceed the fixed c count. If it changes neither a nor b, it removes at least one c when pumped down, leaving at most p c symbols. Each case violates L₁; any loss of block order also violates it.

**4. Conclude.** L₁ is not context-free, while L₂ is. **Answer: C.** Merely saying “two comparisons are needed” is intuition; the pumping argument establishes the non-context-free claim.

More Regular and Context-Free Languages, Pumping Lemma questions

All Regular and Context-Free Languages, Pumping Lemma questions →