GATE 2025 CS2 Q.52: solution and answer

GATE 2025 · CS2Q.52 · 2 marks · MSQ

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

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

(A)
${a^{m} b^{n} ∣ m, n \geq 0}$
(B)
${a, b}^{*} \cap {a^{m} b^{n} c^{m - n} ∣ m \geq n \geq 0}$
(C)
${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{b} (w) \equiv 3 (mod 9)}$
(D)
${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{a} (w) = #_{b} (w)}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The regular languages are (A) and (C).

Official answer: A, CSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

(A) ${a^{m} b^{n} ∣ m, n \geq 0}$ is exactly the language of the regular expression $a^{*} b^{*}$ , so it is regular.
(B) A string in ${a, b}^{*}$ has no $c$ , so a string $a^{m} b^{n} c^{m - n}$ can lie in ${a, b}^{*}$ only when $m - n = 0$ . The intersection is therefore ${a^{n} b^{n} ∣ n \geq 0}$ . This language is not regular, by the pumping lemma. So (B) is not regular.
(C) The two conditions count different letters, so they can be tracked independently. A DFA keeps the pair $(#_{a} mod 7, #_{b} mod 9)$ in $7 \times 9 = 63$ states. It starts at $(0, 0)$ , reading $a$ adds 1 to the first coordinate (mod 7), reading $b$ adds 1 to the second coordinate (mod 9), and the only accepting state is $(2, 3)$ . So (C) is regular.
(D) Call the language $L_{D}$ . Regular languages are closed under intersection, so if $L_{D}$ were regular then $L_{D} \cap a^{*} b^{*}$ would be regular. A string $a^{i} b^{j}$ in $L_{D}$ needs $i = j$ and $i \equiv 2 (mod 7)$ , so $L_{D} \cap a^{*} b^{*} = {a^{n} b^{n} ∣ n \equiv 2 (mod 7)}$ .
This language is not regular. Suppose it had pumping length $p_{0}$ . Choose $n \geq p_{0}$ with $n \equiv 2 (mod 7)$ and let $w = a^{n} b^{n}$ . The pumped part $y$ lies inside the first $p_{0}$ symbols, so $y = a^{k}$ with $k \geq 1$ . Then $x y^{2} z = a^{n + k} b^{n}$ has $#_{a} \neq = #_{b}$ , so it is not in the language. This contradicts the pumping lemma, so $L_{D} \cap a^{*} b^{*}$ is not regular, and therefore $L_{D}$ is not regular.
The regular languages are (A) and (C).

KEY IDEA

Check each language by either giving a finite automaton (independent modular counters give a product DFA) or by intersecting with a simple regular set to expose a non-regular core such as $a^{n} b^{n}$ .

WATCH OUT FOR

Treating (D) as regular because of the mod 7 condition, or missing that in (B) the intersection with ${a, b}^{*}$ removes every $c$ and forces $m = n$ , which leaves $a^{n} b^{n}$ .

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 5 Regular languages questions, with notes

GATE 2025 CS2 Q.52: solution and answer

Answer and solution

More Regular languages questions