# 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. Dec 6, 2014 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. Dec 6, 2014 at 8:49
• @jinxuanWu You should put that line of thought in the question. Dec 6, 2014 at 9:10

## 1 Answer

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

• I got the impression that @jinxuanWu wanted to adapt the proof to show that every word has its own equivalence class; leaving the proof as is does not satisfy this. Dec 6, 2014 at 18:36
• @Raphael: What do you mean? This is the proof that every word forms its on class in the MN relation. Dec 6, 2014 at 19:02
• @Raphael If that is indeed the question, it has been answered here: What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class? But I was under the impression the question was on a detail in that proof? Dec 7, 2014 at 0:49