A language is regular exactly when indistinguishability by all suffixes has finitely many equivalence classes; these classes form its minimal DFA.
For a language , defineThis is a right congruence, and its equivalence classes are the states of the minimal deterministic finite automaton for .
Articles by others on the same topic
The Myhill–Nerode theorem is a fundamental result in formal language theory that provides a characterization of regular languages in terms of equivalence relations on strings. It offers a method to determine whether a language is regular and to construct the minimal deterministic finite automaton (DFA) that recognizes a given regular language.