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.
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ You don't need to find the equivalence classes of the language. It suffices to find infinitely many words which are pairwise distinguishable. $\endgroup$– Yuval FilmusCommented Mar 23, 2018 at 11:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
