GATE CS 2025 Set 1 Q.45: Context-Free Grammars, Pushdown Automata and CFLs

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?

Both $L_1$ and $L_2$ are context-free languages.

$L_1$ is a context-free language but $L_2$ is not a context-free language.

$L_1$ is not a context-free language but $L_2$ is a context-free language.

Neither $L_1$ nor $L_2$ are context-free languages.

Official answer and solution

Solution

Rewrite the exponent $m+n$ of $c$ and check whether a single stack can verify the constraints.

Analysis of $L_1$ :
- $L_1 = \{a^m b^m c^k \mid m \ge 1,\; k > m\}$ requires simultaneously checking that the number of $a$ 's equals the number of $b$ 's and that the number of $c$ 's is strictly greater than $m$ . A single-stack PDA loses the count $m$ once it pops the $a$ 's against the $b$ 's, so $L_1$ is not a context-free language.
Analysis of $L_2$ :
- We can rewrite $L_2 = \{a^m b^n c^n c^m \mid m, n \ge 1\}$ .
- A PDA can push all $m$ $a$ 's onto the stack, then push all $n$ $b$ 's onto the stack, then pop the $n$ $b$ 's against the first $n$ $c$ 's, and finally pop the $m$ $a$ 's against the remaining $m$ $c$ 's (generated by the CFG $S \to aSc \mid aAc, \; A \to bAc \mid bc$ ). Thus $L_2$ is a context-free language.

Final answer

Option (C)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 45 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.