Basic Myhill-Nerode Theorem Practice

I wanted to understand the Myhill-Nerode Theorem so I made up a small example to do so.


L = (a $+$ b )

Clearly, this language is regular. So, I should be able to establish a finite number of equivalence classes by using this method.

I start with a suffix of length 0, which is only $\lambda$:

a$\lambda$ = a $\in$ L

b$\lambda$ = b $\in$ L

For all suffix strings of length $\nu \gt 0$, both are not elements of L.
Therefore, there are no distinguishable strings. I suspect this means there are 0 equivalence classes, and since 0 is a finite number, the language is regular. What might be missing from this analysis?

Note: I made sure to do some online research already and feel comfortable with the ideas of distinguishable strings. The equivalence class bit is what I probably need some clarification on.

What you show is that $a$ and $b$ belong to the same equivalence class. Indeed, in this case there are exactly three equivalence classes: $\{\lambda\}$, $\{a,b\}$, and $\{ w : |w| \geq 2 \}$ (that's assuming the alphabet is $\{a,b\}$). I'll leave it as an exercise to prove that.

The Myhill–Nerode equivalence classes are intimately related to the minimal DFA. Indeed, given the minimal DFA, the number of equivalence classes equals the number of states, and each equivalence class consists of all strings which end up at that state. That's the quickest way to find the equivalence classes in simple cases such as $a+b$.

StackExchange Computer Science Q#48340, answer score: 2