Discussion

Answer: C

The correct statement is L₁ is not regular, but L₂ is regular.

L₂ is regular. Here \(\alpha\) is a string of a's only, so a word \(\alpha\beta\alpha\) starts and ends with a. Conversely, any word over {a, b} that starts with a, ends with a and has length at least 3 can be written with \(\alpha = a\) and \(\beta\) the nonempty middle. So L₂ is the language of the expression \(a(a + b)^{+}a\), which is regular.

L₁ is not regular. Now \(\alpha\) can be any string over {a, b}, so the first and last symbols of a word need not be equal. Take the words \(a b^{i} a a b^{j}\) with \(i, j \ge 1\). Such a word ends in b, so \(\alpha\) must end in b, and being a prefix \(\alpha\) must start with a. The only suffix starting at an a and ending in b that is short enough is \(a b^{j}\) (the longer suffix \(a a b^{j}\) would need the word to start with aa, but it starts with ab). That \(\alpha\) is also a prefix exactly when \(i \ge j\), and then the middle part is nonempty. So

\[ \begin{aligned} L_{1} \cap a b^{+} a a b^{+} &= \\ & \{ a b^{i} a a b^{j} \mid i \ge j \ge 1 \} \end{aligned} \]

This language is not regular, since a finite automaton cannot compare the number of b's before and after the aa. Regular languages are closed under intersection with the regular language \(a b^{+} a a b^{+}\), so if L₁ were regular this intersection would be regular. Hence L₁ is not regular.

The easy mistake is to read L₁ as the words whose first and last symbols are equal, which is regular. That ignores that \(\alpha\) may have several symbols and that only the word as a whole has to start and end with the same string \(\alpha\). So option C is correct, and A, B and D are not.