Let = \a, b, c\. For x ∈ ^*, and ∈ , let \#_(x) denote the number of occurrences of in x. Which one or more of the following option(s) define(s) regular language(s)?

\w w ∈ \a, b\^*, \#_a(w) 2 7, and \#_b(w) 3 9\

\a, b\^* \a^m b^n c^m-n m ≥ n ≥ 0\

\w w ∈ \a, b\^*, \#_a(w) 2 7, and \#_b(w) 3 9\

\w w ∈ \a, b\^*, \#_a(w) 2 7, and \#_a(w) = \#_b(w)\

GATE CSE 2025 Session 2 Q52: Which counting-based languages are regular

Theory of Computation
2 marks
MSQ
No negative marking

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

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, C (official GATE 2025 final answer key)

Concept used: Counting modulo a constant needs finitely many states; comparing two unbounded counts does not.

First step: Simplify (B): with no $c$ allowed, $m = n$ , giving $\{a^n b^n\}$ ; for (C) build a product DFA with $7 \times 9$ states.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2025 Session 2 questions →

GATE CSE 2025 Session 2 Q52: Which counting-based languages are regular

Question

Full step-by-step solution

More Theory of Computation PYQs