The GATE Grind

GATE 2025 CS (CS2) – Question 52

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 2 marks · Multiple select

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)?

  1. $\{a^m b^n \mid m, n \ge 0\}$
  2. $\{a,b\}^* \cap \{a^m b^n c^{m-n} \mid m \ge n \ge 0\}$
  3. $\{w \mid w \in \{a,b\}^*,\ \#_a(w) \equiv 2 \pmod 7,\ \text{and}\ \#_b(w) \equiv 3 \pmod 9\}$
  4. $\{w \mid w \in \{a,b\}^*,\ \#_a(w) \equiv 2 \pmod 7,\ \text{and}\ \#_a(w) = \#_b(w)\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\{a^m b^n \mid m, n \ge 0\}$; (C) $\{w \mid w \in \{a,b\}^*,\ \#_a(w) \equiv 2 \pmod 7,\ \text{and}\ \#_b(w) \equiv 3 \pmod 9\}$

Explanation

A is $a^*b^*$, which is regular. C is regular via a product DFA tracking the counts mod 7 and mod 9. B reduces to $\{a^nb^n\}$ since no c is allowed, and D requires unbounded counting of equal a's and b's, so both are non-regular.