# Proving a language is not regular using Myhill Nerode Theorem

Let $$L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$$, show that $$L$$ is not regular using Myhill-Nerode relation.

I don't know how to show that $$L$$ has infinite equivalence classes because $$\alpha$$ is a palindrome. I tried to use something like this, but I don't know if its correct:

$$\alpha \equiv_{L} \beta \iff \alpha (aba)^k \in{L} \iff \beta (aba)^k \in{L}$$ $$\forall k \in \mathbb N$$ which implies that for every k there exists an equivalence class because the repetition of aba k times.

## 2 Answers

Take $$a^nb$$ and $$a^mb$$ for n != m. Since the first can be followed by $$a^n$$ and the second can’t, they are in different equivalence classes. Therefore the number of equivalence classes is not finite.

C isn’t even needed.

You seem to have forgotten the letter $$c$$ inside your parenthesis. According to this university handout, an equivalence class requires that appending every string in the alphabet to the two equivalent inputs still makes these two inputs either both in the language or both not in the language. In other words,

$$\alpha \equiv_L \beta$$ means $$\alpha y \in L \wedge \beta y \in L$$ for any $$y$$ in your three letter alphabet, or $$\alpha y \not\in L \wedge \beta y \not\in L$$.

$$y = (aba)^k$$ is not all possible string in the alphabet.

One strategy in the handout is to start with one equivalence class and append the same string to two members of the equivalence class. Then show that the resulting two strings are no longer equivalent, ie. one is in the language while the other one is not. It is a proof by contradiction by first assuming the language is regular.