Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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. We can assume that $|a| \geq |b|$.
If $b$ is not a prefix of $a$ then $aa^R \in L$ but $ba^R \notin L$, since otherwise $ba^R = (ba^R)^R = ab^R$, implying that $b$ is a prefix of $a$.
If $b$ is a prefix of $a$ then $|b| < |a|$, since otherwise $b = a$. Let $\tau$ be a letter such that $b\tau$ is not a prefix of $a$ (i.e., if $a = bx$, where $x \neq \epsilon$, let $\tau$ be some letter different from the initial letter of $x$). Then $a\tau a^R \in L$ but $b\tau a^R \notin L$, since otherwise $b\tau a^R = (b\tau a^R)^R = a \tau b^R$, implying that $b\tau$ is a prefix of $a$.
