Eine Sprache ist genau dann regulär, wenn die Nerode-Äquivalenz zu nur endlich viele Äquivalenzklassen hat.
Die Anzahl dieser Klassen ist gleich der Zustandszahl des minimalen DFA für .
Jede unterscheidbare Restklasse wird ein Zustand im minimalen Automaten.