[Solved]: What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?

Problem Detail: 

I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language accepting palindromes is in its own Myhill-Nerode class?

Thanks

Asked By : new_user

Answered By : Yuval Filmus

There is no "method". You need to use an ad hoc proof, that for each pair of words $a,b$ comes up with a word $w$ such that either $aw \in L$ and $bw \notin L$ or vice versa. In this case, one way is as follows. Suppose we are given two words $a,b$. Consider the word $0^na^R$. For each $n$, $a0^na^R$ is a palindrome. If $n$ is large enough, then one can show that $b0^na^R$ is not a palindrome (when $n$ is small then it could be, consider $a=01$, $b=0$, $n=0$). In other cases, a different argument will be needed.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33414

 Ask a Question

 Download Related Notes/Documents