Theory of Computation
Finite Automata & Regular Languages
GATE 2014
Medium
Which one of the following is TRUE?
- AThe language L = {aⁿbⁿ | n ≥ 0} is regular.
- BThe language L = {aⁿ | n is prime} is regular.
- The language L = {w | w has 3k+1 b's for some k∈ℕ, with Σ={a,b}} is regular.
- DThe language L = {ww | w∈Σ* with Σ={0,1}} is regular.
Explanation
aⁿbⁿ is the classic non-regular language (pumping lemma fails). aⁿ for n prime is not regular (primes aren't eventually periodic). ww is a classic non-regular language (needs unbounded comparison of two halves). But 'number of b's ≡ 1 (mod 3)' is regular — a 3-state counter DFA tracking b-count mod 3 (ignoring a's) suffices.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.