Project ForgeSign up free
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.

Start revising free