finite automata – Prove that language is irregular

For $i ge 0$ define $w_i = b^i aa$.
For any $i,j ge 0$ with $i neq j$ you have what $b^i$ is a distinguishing extension for $w_i$ and $w_j$. Indeed $w_i b^i notin L_2$ but $w_ib^j in L_2$.

Then the number of equivalence classes of the set ${ w_i mid i ge 0}$ with respect to the equivalence relation “having a distinguishing extension” is not finite and, by the Myhill-Nerode theorem, $L_2$ is not regular.


Here is an alternative solution that uses closure properties and the pumping lemma following the hint of Hendrik Jan.

Suppose that $L_2$ is regular. Then so is $L’ = overline{L}_2 cap {b^i aa b^j} = {b^i aa b^i}$, which is easily shown to be non-regular using the pumping lemma.

Indeed, suppose that $L’$ was regular, and let $p$ be its pumping length. For some $k in {1, dots, p}$, the word $b^p aa b^p in L’$ can be written as $b^k b^{p-k} aa b^p$ such that $b^{ki} b^{p-k} aa b^p in L’$ for every $i ge 0$. Nevertheless, for $i=0$ we have $b^{p-k} aa b^p notin L’$, yielding a contradiction.