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)?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2025 Set 2 · Q52
Time
Select all that applyOne or more correct
Solution
Official answer: A) {am bn m, n ≥ 0}; C) {w w ∈ {a, b}*, \#a(w) 2 (mod 7), and \#b(w) 3 (mod 9)}
Regular and Context-Free LanguagesLet us analyze each of the given languages:
Option (A): The language is , which corresponds directly to the regular expression . Since it can be generated by a regular expression, it is regular.
Option (B): The language is . Any string in that contains no occurrences of the symbol must satisfy . Thus, the intersection evaluates to , which is well-known to be non-regular (requires unbounded memory to match the counts of and ).
Option (C): The language is . This is the intersection of two regular languages (one keeping track of the count of 's modulo , requiring states, and the other keeping track of the count of 's modulo , requiring states). A product DFA with states can recognize it, so it is regular.
Option (D): The language requires strings over to satisfy both and . If we intersect this language with the regular language , we get . Using the Pumping Lemma, this language is non-regular; hence the original language is not regular.
Therefore, the correct options are A and C.
Try the question first, then check your work.
Examiner trap
Check whether each language can be accepted by a finite state automaton with a finite number of states. For intersections, evaluate what the resulting set of strings simplifies to.
This Regular and Context-Free Languages previous year question is Q52 of the GATE CSE 2025 Set 2 paper. Find more GATE CSE PYQs on Regular and Context-Free Languages in Theory of Computation, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Regular and Context-Free Languages PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Regular and Context-Free Languages has 21 GATE CSE PYQs across 13 papers from 2011 to 2026. 4 of them are 2-mark MSQs like this one, and GATE CSE 2025 Set 2 has 2.
How GATE tests Regular and Context-Free LanguagesIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.