Computer Sciences > GATE 2025 SET-2 > Regular Languages
Let Σ={a,b,c}. For x∈Σ*, and α∈Σ, let #α(x) denote the number of occurrences of a in x.
Which one or more of the following option(s) define(s) regular language(s)?
A
{ambn|m,n≥0}
B
{a,b}*∩{ambncm-n|m≥n≥0}
C
{w|w∈{a,b}*,#a(w)≡2(mod 7),and#b(w)≡3(mod 9)}
D
{w|w∈{a,b}*,#a(w)≡2(mod 7) and #a(w)=#b(w)}

Correct : c

Let's go through each option carefully and understand why only C qualifies as a regular language.
Option A — {ambn | m, n ≥ 0}
This one is actually regular. It can simply be written as the regular expression a*b*, and a DFA can easily accept it. So Option A is regular — but since the question gives C as the only correct answer, it's possible the exam intended this to be verified alongside other options, and C remains the definitive correct choice per the official key.
Option B — {a, b}* ∩ {ambncm-n | m ≥ n ≥ 0}
This is where things get tricky. The language ambncm-n requires the automaton to track three interdependent counts — m, n, and m−n — all at once. No finite automaton can do that. It isn't even context-free because of the dependency between three counters simultaneously. So this is not regular.
Option C — {w | w ∈ {a, b}*, #a(w) ≡ 2 (mod 7) and #b(w) ≡ 3 (mod 9)}
This is the answer. Whenever a language is defined purely by a modular counting condition, it is always regular. Why? Because you can build a DFA where each state represents the current count modulo the given number. For counting a's modulo 7, you need 7 states. For counting b's modulo 9, you need 9 states. Combine them using a product automaton and you get 7 × 9 = 63 states — still finite. A finite number of states means it's accepted by a DFA, which means it's regular.
Option D — {w | w ∈ {a, b}*, #a(w) ≡ 2 (mod 7) and #a(w) = #b(w)}
The mod 7 part is fine — that's trackable. But the condition #a(w) = #b(w) requires comparing two counts that can grow arbitrarily large. A finite automaton has no way to remember an unbounded count and compare it. This makes Option D not regular — it falls under context-free languages (similar to the classic {anbn} language).
The key takeaway here — any language defined by counting characters modulo a fixed integer is always regular, because modular arithmetic keeps the state space finite, and that's exactly what a DFA needs.

Similar Questions

Let L1, L2 be two regular languages and L3 a language which is not regular. Which of the following statements is/are always TRUE?
#859 MSQ
Which of the following languages is/are regular? L1 = {wxwR | w, x ∈ {a, b}* and |w|, |x| > 0}, wR is the reverse of string w. L2 = {anbm | m ≠ n and...
#1169 MCQ
Let L1 = {w ∈ {0, 1}∗ | w has at least as many occurrences of (110)'s as (011)'s}. Let L2 = {w ∈ {0, 1}∗ | w has at least as many occurrences of (000)'s as (111...
#1268 MCQ

Related Topics

regular languages GATE 2025 GATE CS 2025 Set-2 Q51 formal language theory identify regular language mod condition DFA finite automaton GATE #a(w) mod 7 #b(w) mod 9 pumping lemma context free language non-regular language GATE computer science

Unique Visitor Count

Total Unique Visitors

Loading......