1
$\begingroup$

If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?

$\endgroup$
  • $\begingroup$ @Apass.Jack Equivalence Classes (EC) form a partition (in this case of Σ*). So yes, there are EC's to the languages you mentioned and by the MN theorem every regular language has at least one infinite EC (i'm asking that exact question but for CFL's). $\endgroup$ – Euclid Oct 2 '18 at 21:15
  • $\begingroup$ You cannot prove it since it's false. The language of palindromes over a non-unary alphabet is context-free, but every Myhill–Nerode class is a singleton. $\endgroup$ – Yuval Filmus Oct 3 '18 at 2:46
5
$\begingroup$

The language of palindromes over $\{0,1\}$ is context-free, but every Myhill–Nerode class is a singleton. So your claim is wrong for context-free languages (unless the alphabet is unary). In contrast, regular languages have a finite number of Myhill–Nerode classes, so at least one of them has to be infinite. The same is true for context-free languages over a unary alphabet, since all of them are regular.

$\endgroup$

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.