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$ – user92484 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
4
$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

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