GATE CS 2025 Set 1 Q35 — Regular and Context-free Languages

To determine if the languages are context-free, we analyze the memory requirements for each language:

Analysis of $L_1 = \{a^m b^m c^{m+n} \mid m, n \geq 1\}$:

• In $L_1$, we must ensure that the number of $a$'s equals the number of $b$'s ($m$).
• Additionally, we must compare the count of $c$'s ($m+n$) with the count of $a$'s (or $b$'s) to ensure there are at least $m$ occurrences of $c$.
• Since a Pushdown Automaton (PDA) has only one stack, it cannot perform both comparisons (matching $a$'s with $b$'s, and then matching the count of $a$'s with $c$'s) simultaneously. Thus, $L_1$ is not a context-free language (which can be formally proven using the Pumping Lemma).

Analysis of $L_2 = \{a^m b^n c^{m+n} \mid m, n \geq 1\}$:

• In $L_2$, the number of $c$'s is the sum of the number of $a$'s and $b$'s.
• A PDA can easily recognize this by pushing all $a$'s and $b$'s onto the stack, and then popping one symbol for each incoming $c$.
• We can also write a Context-Free Grammar (CFG) for $L_2$: $$\begin{aligned} S &\to aSc \mid aAc \\ A &\to bAc \mid bc \end{aligned}$$ Since a CFG exists, $L_2$ is a context-free language.

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