Myhill–Nerode theorem

{{short description|Necessary and sufficient condition for a formal language to be regular}}

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 1957 {{harv|Nerode|Sauer|1957|p=ii}}.

Statement

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 {{harv|Hopcroft|Ullman|1979}}.

{{Math theorem

| name = Myhill, Nerode (1957)

| note =

| math_statement = (1) $L$ is regular if and only if $\sim_L$ 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 $L$ .

(3) The minimal DFA is unique up to unique isomorphism. That is, for any minimal DFA acceptor, there exists exactly one isomorphism from it to the following one:

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

}}

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,{{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

}}{{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

}} in honor of Anil Nerode.

{{Math proof|title=Proof|proof=

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

Conversely, if $\sim_L$ 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 $A$ , we construct an isomorphism to the canonical one.

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

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

Now this gives us a bijection between states of $A$ 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. The isomorphism is unique, since for both DFA, any state is reachable from the starting state for some word $x$ .

}}

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 $\sim_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 representations of numbers that can be divided by 3 is regular. Given two binary strings $x, y$ , extending them by one digit gives $2x + b, 2y + b$ , so $2x + b \equiv 2y + b \mod 3$ iff $x \equiv y \mod 3$ . Thus, $00$ (or $11$ ), $01$ , and $10$ are the only distinguishing extensions, resulting in the 3 classes. 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 $L$ the relation $\sim_L$ 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.{{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.

References

{{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}}. 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}}.

Myhill–Nerode theorem

Statement

Use and consequences

Generalizations

See also

References

Further reading