Let Sigma = {a, b, c}. For z in Sigma*, and alpha in Sigma, let #_alpha(z) denote the number of occurrences of alpha in z. Which one or more of the following option(s) define(s) regular language(s)?
A. {a^m b^n c^p | m, n >= 0}
B. {a^(m+n) b^n c^p | m, n >= 0}
C. {w in Sigma* | #_a(w) = 3 * #_b(w), and #_c(w) = 0}
D. {w in Sigma* | #_a(w) mod 3 = #_b(w) mod 7}
GATE 2025 · Theory of Computation · Regular Language · medium
Answer: A and D define regular languages.
Analyze Language A: Language A: {a^m b^n c^p | m, n >= 0}. If p has no lower bound restriction, this is a* b* c* which is clearly regular. Even if p >= 1, it is a* b* c^+ which is also regular. No counting constraint involving equality is required.
Analyze Language B: Language B: {a^(m+n) b^n c^p | m, n >= 0}. This can be rewritten as {a^k b^n c^p | k >= n >= 0, p >= 0}. The condition k >= n requires knowing that the number of a's is at least the number of b's. By the pumping lemma, consider s = a^p b^p c^p. Pumping the a-part increases a-count but not b-count, staying in the language. However, pumping the b-part would violate k >= n. A formal argument shows this requires unbounded counting and is NOT regular.
Analyze Language C: Language C: {w | #_a(w) = 3 * #_b(w) and #_c(w) = 0}. This is a subset of {a,b}* where the number of a's is exactly 3 times the number of b's. To recognize this, a finite automaton would need to track the difference (#_a - 3*#_b), which is unbounded. By the pumping lemma, taking w = a^(3p) b^p and pumping the leading a's creates a string where the ratio is violated. This is NOT regular.
Analyze Language D: Language D: {w | #_a(w) mod 3 = #_b(w) mod 7}. A DFA can track (count_a mod 3, count_b mod 7) as its state. There are 3 * 7 = 21 such pairs. On reading 'a', increment count_a mod 3; on reading 'b', increment count_b mod 7; on reading 'c', neither changes. The accepting states are those where count_a mod 3 = count_b mod 7. This DFA has finitely many states, so D is REGULAR.
Conclusion: Regular: A and D. Non-regular: B and C.