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

L2 = a^m (b^n c^n) c^m is generated by nested matching, so it is CFL (S→aSc | aTc, T→bTc | bc). L1 needs #a=#b and #c>#a simultaneously, which needs two independent comparisons, so it is not CFL (pumping lemma).