Myhill–Nerode theorem

The Myhill–Nerode theorem characterizes regular languages by the finite index of their right-congruence relation. Its equivalence classes correspond exactly to the states of the language’s minimal deterministic finite automaton.

Right congruence: An equivalence relation preserved when the same string is appended to equivalent strings. The theorem’s indistinguishability relation is a right congruence.
Regular language: A language recognized by a finite automaton, equivalently described by a regular expression. The theorem identifies exactly which languages have finitely many equivalence classes.
DFA minimization: The process of merging equivalent states in a deterministic finite automaton to obtain an equivalent minimal machine. The theorem explains why equivalent prefixes can share one state and inequivalent ones cannot.
John Myhill: An American mathematician whose work included early results on finite automata and formal languages. The theorem’s name reflects his independent contribution to its development.
Regular expression equivalence: The decision problem of determining whether two regular expressions denote the same language. It compares descriptions, while the theorem characterizes a language through its distinguishable prefixes.
Myhill–Nerode equivalence: For a language, two strings are equivalent when every possible suffix either makes both strings members or neither. This is the relation whose number of classes determines regularity.
Deterministic finite automaton: A finite-state machine that reads one input symbol at a time and has a unique next state for each symbol. The theorem translates equivalence classes into states of a deterministic machine.
Automaton minimization algorithm: An algorithm that computes a smallest deterministic finite automaton equivalent to a given finite automaton. Partition-refinement methods operationalize the theorem’s state-equivalence principle.
Anil Nerode: An American mathematician known for work in automata theory, logic, and computability. His 1958 work established the characterization now associated with the theorem.
Kleene's theorem: The theorem that finite automata and regular expressions define exactly the same class of languages. It connects two representations; Myhill–Nerode additionally identifies the minimal number of states.

Linked from 5 pages

Ogden's lemmaCompared with: It characterizes regularity directly, unlike Ogden's lemma's pumping-based obstruction method.