GATE CSE 2025 Session 1 Q44: Regularity of αβα languages over {a, b}

Answer: C (official GATE 2025 final answer key)

Concept used: A finite automaton can remember a bounded amount of information: a repeated block of a's can be shrunk to one $a$, but an arbitrary repeated string cannot.

First step: For $L_2$, every $a^k \beta a^k$ equals $a(a^{k-1}\beta a^{k-1})a$, so $L_2 = a(a+b)^+a$. For $L_1$ the repeat cannot be shrunk: with $\alpha = ab$, $\beta = a$ the string $abaab$ starts with $a$ but ends with $b$, so the automaton would have to remember a whole prefix; apply the pumping lemma to $a^n b\, a\, a^n b$.