Question 25

Let us evaluate the four languages:

• (A) $L = \{a^n b^n \mid n \ge 0\}$: This requires counting and matching the number of $a$'s and $b$'s. A finite automaton cannot store arbitrarily large counts, so this is not regular (it is deterministic context-free).

• (B) $L = \{a^n \mid n \text{ is prime}\}$: The set of primes does not form an arithmetic progression. By the pumping lemma, this unary language is non-regular.

• (C) $L = \{w \mid w \text{ has } 3k + 1\text{ } b\text{'s for some } k \in \mathbb{N} \text{ with } \Sigma = \{a, b\}\}$: This condition requires the number of $b$'s to be congruent to $1 \pmod 3$. A DFA with 3 states $\{q_0, q_1, q_2\}$ representing $(N_b(w) \bmod 3)$, with $q_0$ as start state and $q_1$ as the only accepting state, precisely recognizes this language. Therefore, this language is regular.

• (D) $L = \{ww \mid w \in \Sigma^*\}$: Recognizing the duplication of an arbitrary string requires unbounded memory to store $w$, so this is not regular (in fact, not even context-free).

Thus, only statement C is TRUE.