GATE 2025 CS (CS2) – 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)?
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) $\{a^mb^n\mid m,n\ge0\}=a^*b^*$:** regular.
- **(B) $\{a,b\}^*\cap\{a^mb^nc^{m-n}\}$:** because the first language has no `c`, we need $m-n=0$, i.e. $m=n$. This is $\{a^nb^n\}$, which is not regular.
- **(C) $\#_a\equiv2\pmod7$ and $\#_b\equiv3\pmod9$:** a DFA with $7\times9=63$ states tracks $(\#_a\bmod7,\#_b\bmod9)$. Regular.
- **(D) $\#_a\equiv2\pmod7$ and $\#_a=\#_b$:** the equality $\#_a=\#_b$ needs an unbounded counter (the language $\{w:\#_a(w)=\#_b(w)\}$ is not regular, and intersecting with a regular language does not make it regular here). Not regular.
Answer: A, C.
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2024 CS (CS1) Q23
- GATE 2023 CS Q24
- GATE 2022 CS Q23
- GATE 2022 CS Q47
- GATE 2022 CS Q48
- GATE 2021 CS (CS1) Q11
All Regular and Context-Free Languages, Pumping Lemma questions →