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?


  • $\begingroup$ Are you sure you mean DPDA rather than DFA? There are languages accepted by DPDA which have infinitely many Myhill-Nerode equivalence classes, like $\{a^nb^n : n \geq 0\}$. $\endgroup$ Nov 23 '14 at 1:49
  • $\begingroup$ @YuvalFilmus The statement here is not very clear, but it reminds me of I result I have seen that matches this context. A language for which each Myhill-Nerode equivalence class is of finite cardinality cannot be a DCFL. $\endgroup$ Nov 23 '14 at 13:06
  • $\begingroup$ Correct, I do mean DPDA. Since palindromes have a finite number of strings in each myhill-nerode class they are not in DCFL. I'm trying to extend this to show that each string is in a class of its own. Its part of a proof in a book by Jeffery Shallit. He provides a method for showing how languages with finite myhill-nerode classes cannot have a DPDA, but challenges the reader to show that palindromes have only one string in each class. Easy enough concept to understand, but I'm not sure how to generalize it enough to form a proof. $\endgroup$
    – new_user
    Nov 23 '14 at 17:17

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


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.