 Myhill–Nerode theorem

A language is regular exactly when indistinguishability by all suffixes has finitely many equivalence classes; these classes form its minimal DFA.

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.