Myhill–Nerode theorem

In the theory of formal languages, the Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The theorem is named for John Myhill and Anil Nerode, who proved it at the University of Chicago in 1958 (Nerode 1958).

Statement of the theorem

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 R_L on strings by the rule that x R_L y if there is no distinguishing extension for x and y. It is easy to show that R_L is an equivalence relation on strings, and thus it divides the set of all finite strings into equivalence classes.

The Myhill–Nerode Theorem states that L is regular if and only if R_L has a finite number of equivalence classes, and moreover that the number of states in the smallest deterministic finite automaton (DFA) recognizing L is equal to the number of equivalence classes in R_L. In particular, this implies that there is a unique canonical DFA with minimum number of states.

The intuition is that if one starts with such a minimal automaton, then any strings x and y that drive it to the same state will be in the same equivalence class; and if one starts with a partition into equivalence classes, one can easily construct an automaton that uses its state to keep track of the equivalence class containing the part of the string seen so far.

Proof. First, suppose $ A^\ast/\mathcal{N}_L=\{q_0=[\lambda]_{\mathcal{N}_L},\ldots,q_{k-1}\}=Q, $ where is the empty word on A . Construct a DFA =QAq0F (called the Nerode automaton for L ) with :QAQ defined by (1) (qa)=[wa]Lwq and (2) F=qQwLwq Then is well defined because w1Lw2 implies w1uLw2u . It is also straightforward that recognizes L .

On the other hand, let =QAq0F be a DFA that recognizes L . Extend to QA by putting (q)=q and (qaw)=((qa)w) for every qQ , aA , wA . Define f:QAL as $\displaystyle f(q) = \left\{\begin{array}{ll} [w]_{\mathcal{N}_L} & \mathrm{if}... ...ptyset & \mathrm{if}\;\delta(q_0,w)\neq q\forall w\in A^\ast \end{array}\right.$ (1)

Then f is well defined. In fact, suppose q1=q2=q : then either f(q1)=f(q2)= , or there are w1w2A such that (q0w1)=(q0w2)=q . But in the latter case, (q0w1u)=(q0w2u)=(qu) for any uA , hence w1Lw2 since recognizes L . Finally, for any wA we have $ [w]_{\mathcal{N}_L}=f\left(\delta(q_0,w)\right), $ so every class of L has a preimage according to f ; consequently, QAL . $ \Box$==Use and consequences== The Myhill–Nerode theorem may be used to show that a language L is regular by proving that the number of equivalence classes of R_L is finite. This may be done by an exhaustive case analysis in which, beginning from the empty string, distinguishing extensions are used to find additional equivalence classes until no more can be found. For example, the language consisting of binary numbers which can be divided by 3 is regular. Given the empty string, 00 (or 11), 01 and 10 are distinguished extensions resulting in the three classes (corresponding to numbers that give remainders 0, 1 and 2 when divided by 3), but after this step there is no distinguished extension anymore. The minimal automaton accepting our language would have three states corresponding to these three equivalence classes.

Another immediate corollary of the theorem is that if a language defines an infinite set of equivalence classes, it is not regular. It is this corollary that is frequently used to prove that a language is not regular.

See also

• Pumping lemma, an alternative method for proving that a language is not regular

References

• Henzinger, Tom (2003), Lecture 7: Myhill–Nerode Theorem, http://www-cad.eecs.berkeley.edu/~tah/172/7.pdf .
• Hopcroft, John E.; Ullman, Jeffrey D. (1979), "Chapter 3", Introduction to Automata Theory, Languages, and Computation, Reading, Massachusetts: Addison-Wesley Publishing, ISBN 0-201-02988-X .
• Nerode, Anil (1958), "Linear Automaton Transformations", Proceedings of the AMS 9, JSTOR 2033204 .
• Regan, Kenneth (2007), Notes on the Myhill-Nerode Theorem, http://www.cse.buffalo.edu/~regan/cse396/CSE396MNT.pdf .