GATE CS 2025 Set 2 | Question 52

Let \(\Sigma = \{a, b, c\}\). For \(x \in \Sigma^{*}\), and \(\alpha \in \Sigma\), let \(\#_{\alpha}(x)\) denote the number of occurrences of \(\alpha\) in \(x\).

Which one or more of the following option(s) define(s) regular language(s)?

Option A: \(\{a^{m}b^{n} \mid m, n \ge 0\}\) (correct)
Option B: \(\{a, b\}^{*} \cap \{a^{m}b^{n}c^{m-n} \mid m \ge n \ge 0\}\)
Option C: \(\{w \mid w \in \{a, b\}^{*}, \#_{a}(w) \equiv 2 \pmod{7}, \text{ and } \#_{b}(w) \equiv 3 \pmod{9}\}\) (correct)
Option D: \(\{w \mid w \in \{a, b\}^{*}, \#_{a}(w) \equiv 2 \pmod{7}, \text{ and } \#_{a}(w) = \#_{b}(w)\}\)

Answer

(A), (C)

Explanation

(A) is the language of \(a^{*}b^{*}\), so it is regular.
(B) Intersecting with \(\{a, b\}^{*}\) keeps only strings without \(c\), which forces \(m - n = 0\). What remains is \(\{a^{n}b^{n} \mid n \ge 0\}\), which is not regular.
(C) A DFA only has to track \(\#_{a}(w) \bmod 7\) and \(\#_{b}(w) \bmod 9\): a product of two cyclic counters with \(7 \times 9 = 63\) states. Regular.
(D) Requiring \(\#_{a}(w) = \#_{b}(w)\) needs an unbounded counter. If the language were regular, its intersection with \(a^{*}b^{*}\), namely \(\{a^{n}b^{n} \mid n \equiv 2 \pmod{7}\}\), would be regular too; the pumping lemma rules this out, because pumping inside the leading block of \(a\)'s changes the number of \(a\)'s but not of \(b\)'s.

Answer: A, C