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?

  • 2
    $\begingroup$ Are you using in your proof explicitly that $|\Sigma|<3$? I guess not. $\endgroup$ – A.Schulz Dec 6 '14 at 8:34
  • 1
    $\begingroup$ 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. $\endgroup$ – jinxuan Wu Dec 6 '14 at 8:49
  • 1
    $\begingroup$ @jinxuanWu You should put that line of thought in the question. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Raphael Dec 6 '14 at 18:36
  • $\begingroup$ @Raphael: What do you mean? This is the proof that every word forms its on class in the MN relation. $\endgroup$ – A.Schulz Dec 6 '14 at 19:02
  • $\begingroup$ @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? $\endgroup$ – Hendrik Jan Dec 7 '14 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.