# Using Myhill-Nerode to prove that language is not regular

L = {$xy ∈ \{a, b\}^∗ : |x| = |y|$ and x contains the substring aa}

I am trying to prove that this language is not regular using MyHill-Nerode theorem but I am unable to find equivelance classes of this language. Thanks.

• You don't need to find the equivalence classes of the language. It suffices to find infinitely many words which are pairwise distinguishable. Mar 23 '18 at 11:42

Consider two words $u_i = b^i aa, u_j = b^j aa \in \{a, b\}^\ast$ with $i < j$. We have that $u_i \not\sim_L u_j$ because if you concatenate the word $v = b^{i+2}$ to both words we obtain $$u_i \cdot v = b^i aa \cdot b^{i+2} \in L \text{, but } u_j \cdot v = b^j aa \cdot b^{i+2} \notin L.$$ Thus, $v$ separates $u_i$ and $u_j$ for $L$. Since we can find infinitely many $i, j \in \mathbb{N}$ with $i < j$ we have also infinitely many Myhill-Nerode-equivalence classes.