Given a language L, and a pair of strings x and y, define a
distinguishing extension to be a string z such that exactly one of the two strings xz and yz belongs to L. Define a relation \sim_L on strings as x\; \sim_L\ y if there is no distinguishing extension for x and y. It is easy to show that \sim_L is an
equivalence relation on strings, and thus it divides the set of all strings into
equivalence classes. The Myhill–Nerode theorem states that a language L is regular if and only if \sim_L has a finite number of equivalence classes, and moreover, that this number is equal to the number of states in the
minimal deterministic finite automaton (DFA) accepting L. Furthermore, every minimal DFA for the language is isomorphic to the canonical one . Generally, for any language, the constructed automaton is a
state automaton acceptor. However, it does not necessarily have
finitely many states. The Myhill–Nerode theorem shows that finiteness is necessary and sufficient for language regularity. Some authors refer to the \sim_L relation as
Nerode congruence, in honor of
Anil Nerode. L is a regular language, then by definition there is a DFA A that recognizes it, with only finitely many states. If there are n states, then partition the set of all finite strings into n subsets, where subset S_i is the set of strings that, when given as input to automaton A, cause it to end in state i. For every two strings x and y that belong to the same subset, and for every choice of a third string z, the automaton A reaches the same state on input xz as it reaches on input yz, and therefore must either accept both of the inputs xz and yz or reject both of them. Therefore, no string z can be a distinguishing extension for x and y, so they must be related by \sim_L. Thus, S_i is a subset of an equivalence class of \sim_L. Combining this fact with the fact that every member of one of these equivalence classes belongs to one of the sets S_i, this gives a surjective function from states of A to equivalence classes, implying that the number of equivalence classes is finite and at most n. In the other direction, suppose that \sim_L has finitely many equivalence classes. In this case, it is possible to design a deterministic finite automaton that has one state for each equivalence class. The start state of the automaton corresponds to the equivalence class containing the empty string, and the transition function from a state X on input symbol a takes the automaton to a new state, the state corresponding to the equivalence class containing string xa, where x is an arbitrarily chosen string in the equivalence class corresponding to X. The definition of the Myhill–Nerode relation implies that the transition function is well-defined: no matter which representative string x is chosen for state X, the same transition function value will result. A state of this automaton is accepting if the corresponding equivalence class contains a string in L; in this case, again, the definition of the relation implies that all strings in the same equivalence class must also belong to L, for otherwise the empty string would be a distinguishing string for some pairs of strings in the class. Thus, the existence of a finite automaton recognizing L implies that the Myhill–Nerode relation has a finite number of equivalence classes, at most equal to the number of states of the automaton, and the existence of a finite number of equivalence classes implies the existence of an automaton with that many states. --> ==Use and consequences==