GATE CS 2025 Set 2 — Question 52

Option (A): The language $L_A = \{a^m b^n \mid m, n \ge 0\}$ corresponds to the regular expression $a^* b^*$. Since it can be represented by a regular expression, it is a regular language.Option (B): Let $L_1 = \{a, b\}^*$ and $L_2 = \{a^m b^n c^{m-n} \mid m \ge n \ge 0\}$. The intersection $L = L_1 \cap L_2$ consists of strings in $L_2$ that contain only symbols from $\{a, b\}$. For a string $s = a^m b^n c^{m-n}$ to be in $\{a, b\}^*$, the number of $c$'s must be zero. Thus, $m - n = 0$, which implies $m = n$. The resulting language is $L = \{a^n b^n \mid n \ge 0\}$. This is a well-known context-free language that is not regular (can be proved using the Pumping Lemma).Option (C): The condition $\#_a(w) \equiv 2 \pmod 7$ can be checked by a DFA with 7 states. The condition $\#_b(w) \equiv 3 \pmod 9$ can be checked by a DFA with 9 states. The language is the intersection of these two regular languages. Since regular languages are closed under intersection, this language is regular.Option (D): The condition $\#_a(w) = \#_b(w)$ requires comparing the counts of $a$'s and $b$'s, which requires unbounded memory (like a stack). A finite automaton cannot check equality of counts for an arbitrary length string. Thus, this language is not regular.