GATE 2025 CS (CS1) – Question 45
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?
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
- GATE 2025 CS (CS2) Q24
- GATE 2025 CS (CS2) Q30
- GATE 2025 CS (CS2) Q52
- GATE 2024 CS (CS1) Q23
- GATE 2023 CS Q24
- GATE 2022 CS Q23
All Regular and Context-Free Languages, Pumping Lemma questions →