# 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.