View source for Myhill–Nerode theorem

{{short description|Necessary and sufficient condition for a formal language to be regular}}
In the theory of [[formal language]]s, the '''Myhill–Nerode theorem''' provides a [[necessary and sufficient conditions|necessary and sufficient condition]] for a language to be [[regular language|regular]]. The theorem is named for [[John Myhill]] and [[Anil Nerode]], who proved it at the [[University of Chicago]] in 1957 {{harv|Nerode|Sauer|1957|p=ii}}.

==Statement==
Given a language <math>L</math>, and a pair of strings <math>x</math> and <math>y</math>, define a  '''distinguishing extension''' to be a string <math>z</math> such that
exactly one of the two strings <math>xz</math> and <math>yz</math> belongs to <math>L</math>.
Define a relation <math>\sim_L</math> on strings as <math>x\; \sim_L\ y</math> if there is no distinguishing extension for <math>x</math> and <math>y</math>.  It is easy to show that <math>\sim_L</math> is an [[equivalence relation]] on strings, and thus it divides the set of all strings into  [[equivalence class]]es.

The Myhill–Nerode theorem states that a language <math>L</math> is regular if and only if <math>\sim_L</math> has a finite number of equivalence classes, and moreover, that this number is equal to the number of states in the [[minimal automaton|minimal]] [[deterministic finite automaton]] (DFA) accepting <math>L</math>. Furthermore, every minimal DFA for the language is isomorphic to the canonical one {{harv|Hopcroft|Ullman|1979}}.

{{Math theorem
| name = Myhill, Nerode (1957)
| note = 
| math_statement = (1) <math>L</math> is regular if and only if <math>\sim_L</math> has a finite number of equivalence classes.  

(2) This number is equal to the number of states in the minimal deterministic finite automaton (DFA) accepting <math>L</math>.  

(3) Any minimal DFA acceptor for the language is isomorphic to the following one:  

: Let each equivalence class <math>[x]</math> correspond to a state, and let state transitions be <math>a: [x] \to [xa]</math> for each <math>a\in \Sigma</math>. Let the starting state be <math>[\epsilon]</math>, and the accepting states be <math>[x]</math> where <math>x\in L</math>.
}}

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 <math>\sim_L</math> relation as '''Nerode congruence''',<ref>{{citation
 | last1 = Brzozowski | first1 = Janusz|author-link=Janusz Brzozowski (computer scientist)
 | last2 = Szykuła | first2 = Marek
 | last3 = Ye | first3 = Yuli
 | year = 2018
 | title = Syntactic Complexity of Regular Ideals
 | journal = [[Theory of Computing Systems]]
 | pages = 1175–1202
 | volume = 62
 | issue = 5
 | doi = 10.1007/s00224-017-9803-8
| hdl = 10012/12499
 | s2cid = 2238325
 | hdl-access = free
 }}</ref><ref>{{citation
 | last1 = Crochemore | first1 = Maxime
 | last2 = Epifanio | first2 = Chiara
 | last3 = Gabriele | first3 = Alessandra
 | last4 = Mignosi | first4 = Filippo
 | display-authors=1
 | title = From Nerode's congruence to suffix automata with mismatches
 | journal = [[Theoretical Computer Science]]
 | volume = 410
 | number = 37
 | pages = 3471–3480
 | year = 2009
 | doi = 10.1016/j.tcs.2009.03.011
| s2cid = 14277204
 | doi-access = free
 }}</ref> in honor of [[Anil Nerode]].

{{Math proof|title=Proof|proof=

(1) If <math>L</math> is regular. construct a minimal DFA to accept it. Clearly, if <math>x, y</math> end up in the same state after running through the DFA, then <math>x\sim_L y</math>, thus the number of equivalence classes of <math>\sim_L</math> is at most the number of DFA states, which must be finite.  

Conversely, if <math>\sim_L</math> has a finite number of equivalence classes, then the state automaton constructed in the theorem is a DFA acceptor, thus the language is regular.  

(2) By the construction in (1).  

(3) Given a minimal DFA acceptor <math>A</math>, we construct an isomorphism to the canonical one.  

Construct the following equivalence relation: <math>x\sim_A y</math> if and only if <math>x, y</math> end up on the same state when running through <math>A</math>.

Since <math>A</math> is an acceptor, if <math>x\sim_A y</math> then <math>x\sim_L y</math>. Thus each <math>\sim_L</math> equivalence class is a union of one or more equivalence classes of <math>\sim_A</math>. Further, since <math>A</math> is minimal, the number of states of <math>A</math> is equal to the number of equivalence classes of <math>\sim_L</math> by part (2). Thus <math>\sim_A = \sim_L</math>.  

Now this gives us a bijection between states of <math>A</math> and the states of the canonical acceptor. It is clear that this bijection also preserves the transition rules, thus it is an isomorphism of DFA.  
}}
<!-- old proof
If <math>L</math> is a regular language, then by definition there is a DFA <math>A</math> that recognizes it, with only finitely many states. If there are <math>n</math> states, then partition the set of all finite strings into <math>n</math> subsets, where subset <math>S_i</math> is the set of strings that, when given as input to automaton <math>A</math>, cause it to end in state <math>i</math>. For every two strings <math>x</math> and <math>y</math> that belong to the same subset, and for every choice of a third string <math>z</math>, the automaton <math>A</math> reaches the same state on input <math>xz</math> as it reaches on input <math>yz</math>, and therefore must either accept both of the inputs <math>xz</math> and <math>yz</math> or reject both of them. Therefore, no string <math>z</math> can be a distinguishing extension for <math>x</math> and <math>y</math>, so they must be related by <math>\sim_L</math>. Thus, <math>S_i</math> is a subset of an equivalence class of <math>\sim_L</math>. Combining this fact with the fact that every member of one of these equivalence classes belongs to one of the sets <math>S_i</math>, this gives a surjective function from states of <math>A</math> to equivalence classes, implying that the number of equivalence classes is finite and at most <math>n</math>.

In the other direction, suppose that <math>\sim_L</math> 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 <math>X</math> on input symbol <math>a</math> takes the automaton to a new state, the state corresponding to the equivalence class containing string <math>xa</math>, where <math>x</math> is an arbitrarily chosen string in the equivalence class corresponding to <math>X</math>. The definition of the Myhill–Nerode relation implies that the transition function is well-defined: no matter which representative string <math>x</math> is chosen for state <math>X</math>, the same transition function value will result. A state of this automaton is accepting if the corresponding equivalence class contains a string in <math>L</math>; in this case, again, the definition of the relation implies that all strings in the same equivalence class must also belong to <math>L</math>, 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 <math>L</math> 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==
The Myhill–Nerode theorem may be used to show that a language <math>L</math> is [[regular language|regular]] by proving that the number of equivalence classes of <math>\sim_L</math> is finite. This may be done by an exhaustive [[Proof by cases|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 representations of numbers that can be divided by 3 is regular. Given the empty string, <math>00</math> (or <math>11</math>), <math>01</math>, and <math>10</math> are distinguishing 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 distinguishing 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 for a language <math>L</math> the relation <math>\sim_L</math> has infinitely many equivalence classes, it is {{em|not}} regular.  It is this corollary that is frequently used to prove that a language is not regular.

== Generalizations ==
The Myhill–Nerode theorem can be generalized to [[tree automata]].<ref>{{cite book | url=https://hal.inria.fr/hal-03367725 | author1=Hubert Comon |author2= Max Dauchet |author3= Rémi Gilleron |author4=  Florent Jacquemard |author5= Denis Lugiez |author6= Christoph Löding |author7=  Sophie Tison |author8= Marc Tommasi | title=Tree Automata Techniques and Applications (TATA) | date=Oct 2021 }} Here: Sect. 1.5, p.35-36.</ref>

== See also ==
*[[Pumping lemma for regular languages]], an alternative method for proving that a language is not regular. The pumping lemma may not always be able to prove that a language is not regular.
*[[Syntactic monoid]]

== References ==
{{reflist}}
*{{citation
 |last1=Hopcroft |first1=John E. |author1-link=John E. Hopcroft
 |last2=Ullman |first2=Jeffrey D. |author2-link=Jeffrey D. Ullman
 |contribution=Chapter 3.4
 |isbn=0-201-02988-X
 |location=Reading, Massachusetts
 |publisher=Addison-Wesley Publishing
 |title=[[Introduction to Automata Theory, Languages, and Computation]]
 |year=1979}}.
*{{citation
 | last = Nerode | first = Anil | author-link = Anil Nerode
 | journal = [[Proceedings of the American Mathematical Society]]
 | title = Linear Automaton Transformations
 | jstor = 2033204
 | volume = 9
 | year = 1958| issue = 4 | pages = 541–544 | doi = 10.1090/S0002-9939-1958-0135681-9 | doi-access=free}}.
*{{citation
 | url=https://books.google.com/books?id=QjZwISLU4rAC
 | first1=Anil |last1=Nerode 
 | first2= Burton P. |last2= Sauer
 | title=Fundamental Concepts in the Theory of Systems
 | institution=Wright Air Development Center
 | type=WADC Technical Report
 | number=57–624
 | date=Nov 1957}}. [[Armed Services Technical Information Agency|ASTIA]] Document No. AD 155741.
*{{citation
 | last = Regan | first = Kenneth
 | title = Notes on the Myhill-Nerode Theorem
 | url = http://www.cse.buffalo.edu/~regan/cse396/CSE396MNT.pdf
 | year = 2007
 | accessdate = 2016-03-22}}.

==Further reading==
*{{cite book|author1=Bakhadyr Khoussainov|author2=Anil Nerode|authorlink2=Anil Nerode|title=Automata Theory and its Applications|url=https://books.google.com/books?id=wR_oBwAAQBAJ|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4612-0171-7}}
{{DEFAULTSORT:Myhill-Nerode theorem}}
[[Category:Formal languages]]
[[Category:Theorems in discrete mathematics]]
[[Category:Finite automata]]