GATE CS 2001 Q2.6 — Regular and Context-free Languages

To determine which of the given languages are regular, let us analyze each one individually:

• $L_1 = \{ww \mid w \in \{a,b\}^*\}$: This language consists of duplicated strings. To recognize strings in $L_1$, a machine must remember the first half of the string and compare it symbol-by-symbol with the second half in the exact same order. This requires infinite memory and cannot be done by a Finite Automaton (FA). In fact, $L_1$ is not even a Context-Free Language (CFL). Thus, $L_1$ is not regular.


• $L_2 = \{ww^R \mid w \in \{a,b\}^*\}$: This is the language of even-length palindromes. Recognizing $L_2$ requires matching symbols from the center outwards (in reverse order), which requires a stack (infinite memory). While it is a Context-Free Language, $L_2$ is not regular.


• $L_3 = \{0^{2i} \mid i \text{ is a non-negative integer}\}$: Since string lengths must be non-negative, we consider $i \ge 0$. This gives: $$L_3 = \{\epsilon, 00, 0000, 000000, \dots\}$$ This is the set of all strings of $0$s with an even length. It can be represented by the regular expression $(00)^*$ and recognized by a simple 2-state DFA. Thus, $L_3$ is regular.


• $L_4 = \{0^{i^2} \mid i \text{ is a non-negative integer}\}$: The lengths of the strings in this language are perfect squares: $0, 1, 4, 9, 16, \dots$. The gap between consecutive string lengths ($1, 3, 5, 7, \dots$) grows infinitely. By the Pumping Lemma, any regular language over a single-letter alphabet must have string lengths that eventually form an arithmetic progression (i.e., become periodic). Since the sequence of perfect squares is not periodic, $L_4$ is not regular.

Therefore, only $L_3$ is regular, which corresponds to option D.