GATE CS 2025 Set 2 Q42 — Regular and Context-free Languages

We analyze each option to determine if the defined language is regular:

• Option A: The language is $\{a^m b^n \mid m, n \geq 0\}$, which can be represented by the regular expression $a^*b^*$. Thus, it is regular.
• Option B: The second set contains strings of the form $a^m b^n c^{m-n}$ where $m \geq n \geq 0$. Intersecting this set with $\{a, b\}^*$ means we only retain strings that contain no $c$ symbols. This requires the exponent of $c$ to be zero: $$m - n = 0 \implies m = n$$ Thus, the language simplifies to $\{a^n b^n \mid n \geq 0\}$, which is a well-known non-regular language.
• Option C: Let $L_1 = \{w \in \{a, b\}^* \mid \#_a(w) \equiv 2 \pmod 7\}$ and $L_2 = \{w \in \{a, b\}^* \mid \#_b(w) \equiv 3 \pmod 9\}$. Both $L_1$ and $L_2$ are regular because modulo counting can be done using finite state automata (with $7$ and $9$ states, respectively). Since regular languages are closed under intersection, $L_1 \cap L_2$ is regular.
• Option D: This language requires checking the condition $\#_a(w) = \#_b(w)$, which requires infinite memory (a stack) to compare the exact counts of $a$ and $b$. Thus, it is non-regular.