For a formal language , define when exactly when for every suffix . The Myhill-Nerode theorem states that is a regular language exactly when this equivalence relation has finitely many classes.
Each class becomes a state of the minimal deterministic finite automaton, with transition . For strings with an even number of ones, there are two classes, determined by parity. For , the prefixes lie in distinct classes: appending distinguishes from every other such prefix. This proves nonregularity without guessing an automaton.
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.