Consider the following two languages over the alphabet \(\{a, b\}\):
\[ L_1 = \{\, \alpha\beta\alpha \mid \alpha \in \{a, b\}^+ \text{ AND } \beta \in \{a, b\}^+ \,\} \]
\[ L_2 = \{\, \alpha\beta\alpha \mid \alpha \in \{a\}^+ \text{ AND } \beta \in \{a, b\}^+ \,\} \]
Which ONE of the following statements is CORRECT?
Answer
(C)
Explanation
- \(L_2\): \(\alpha\) is a block of a's, so any \(a^k \beta a^k\) can be rewritten with \(\alpha = a\) by moving the extra a's into the middle part. So \(L_2 = {a(a+b)^+a}\), the strings of length at least 3 that start and end with \(a\), which is regular.
- \(L_1\): shrinking \(\alpha\) to one symbol fails, because \(\alpha\) may start and end with different symbols; for example \(abaab = (ab)(a)(ab) \in L_1\). A finite automaton would have to remember an arbitrarily long \(\alpha\).
- Pumping lemma proof for \(L_1\): \(w = a^n b\, a\, a^n b \in L_1\) (\(\alpha = a^n b\), \(\beta = a\)). Pumping up the leading a's gives \(a^{n+k} b\, a^{n+1} b\). Here \(\alpha\) must be a prefix ending in \(b\), i.e. \(a^{n+k} b\), and that is a suffix only when \(k = 1\), when nothing is left for \(\beta\). So the pumped string is not in \(L_1\), and \(L_1\) is not regular.
Answer: C