Which one or more of the following option(s) define(s) regular language(s)?
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
Total Unique Visitors