# Prove that every CFL has at least one infinite equivalence class

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

• @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). – Euclid Oct 2 '18 at 21:15
• 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. – Yuval Filmus Oct 3 '18 at 2:46

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.