Languages having only one Myhill–Nerode equivalence class

Consider the alphabet $$\Sigma = \{a,b\}$$. For which languages does the Myhill–Nerode equivalence relation have exactly one class?

From what I understand about equivalence classes, each state is considered a class. So would $$\{ a^n : n>0\}$$ be the one class?

– D.W.
Commented Apr 13, 2016 at 22:22
• It should be: "for which languages does the Myhill–Nerode equivalence relation have exactly one class?" Commented Apr 14, 2016 at 15:38
• Your example needs three states. aaa would be in an accepting state, eps and aba wouldn’t. You can move from eps to an Commented Feb 15 at 18:50

Let $$L \subseteq \{ a, b\}^*$$ be a language with one Myhill-Nerode equivalence class. You can show that $$L$$ must be trivial, that is $$L\in \{\emptyset, \{a, b\}^*\}$$, either by using the Myhill-Nerode theorem as Yuval did, or by showing that directly. Indeed, as for $$L$$ to have a single Myhill-Nerode equivalence class, it means that for all three words $$x,y$$ and $$z$$ over $$\{ a, b\}$$, it holds that $$x\cdot z \in L \Longleftrightarrow y\cdot z \in L$$
In words, we cannot separate any two words $$x$$ and $$y$$, by any word $$z$$. Hence, $$L$$ must be trivial, because otherwise there are two words $$x\in L$$, and $$y\notin L$$, and for $$z = \epsilon$$, we get that $$x \cdot z = x \in L$$, but $$y\cdot z = y \notin L$$, and we have reached a contradiction.