# Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?

In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \{0,1\}$. $PAL = \{w \in \{0,1\}^* : w = w^R\}$. We have proved that every string in this language will be pairwise inequivalent, i.e. every string is in its own Myhill-Nerode equivalence class.

However, what if we extend this definition to an alphabet $\Sigma$ that contains more than two characters? Can I still claim any 2 distinct strings in $\Sigma^*$ are still pairwise inequivalent?

• Are you using in your proof explicitly that $|\Sigma|<3$? I guess not. – A.Schulz Dec 6 '14 at 8:34
• Actually, the way we prove it is assume a $z = 10^{|x|+|y|+|2|}x^{rev}$. so for every xz, unless y = x otherwise $yz \notin PAL$. The same logic seems apply to alphabet larger than 3. But I think it doesn't. Because Myhill-Nerode relation requires for all $z \in \Sigma^*$, $xz \in L$ if and only $yz\in L$. With the number of elements in alphabet set growing it becomes more harder to define this z. That is what hinders me. – jinxuan Wu Dec 6 '14 at 8:49
• @jinxuanWu You should put that line of thought in the question. – Raphael Dec 6 '14 at 9:10

Your proof goes also through with a larger alphabet. Let $x,y\in \Sigma^*$, with $x\neq y$. We use as $z$ the word $10^{|x|+|y|+2}1x^{rev}$. Clearly, $xz$ is a palindrome and therefore the word is in the language. The word $yz$ however is not a palindrome. Note that the middle of $yz$ there has to be a $0$ coming from $z$, hence for being a palindrome the middle of $yz$ has to be centered between the two $1$s of $z$. As a consequence, $yz$ is a palindrome only if $x=y$. Thus $yz$ is not in the language.
For the proof you only need that $|\Sigma|\ge 2$. I would say having more letters makes it even easier, since you have more possibilities to choose the split word $z$.