GATE CS 2014 Set 1 Q15 — Regular and Context-free Languages

To determine which language is regular, we analyze each option:

• Option A: $L = \{a^n b^n \mid n \geq 0\}$ is a classic non-regular language. It requires infinite memory (a stack) to ensure the number of $a$'s matches the number of $b$'s.
• Option B: $L = \{a^n \mid n \text{ is prime}\}$ is not regular. The gap between consecutive prime numbers grows arbitrarily large, which violates the pumping lemma for regular languages.
• Option C: $L = \{w \mid w \text{ has } 3k+1 \text{ } b\text{'s for some } k \in \mathbb{N}\}$ is regular. We only need to count the number of $b$'s modulo 3. This can be recognized by a Deterministic Finite Automaton (DFA) with 3 states, where the transitions on symbol $a$ remain in the same state, and transitions on $b$ cycle through the states.
• Option D: $L = \{ww \mid w \in \{0,1\}^*\}$ is not regular. It requires remembering the entire first half of the string $w$ to match it with the second half, which cannot be done with finite states.

Thus, only Option C is regular.