Myhill–Nerode theorem

(Redirected from 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 1957 (Nerode & Sauer 1957, p. ii).

Statement

edit

Given a language  , and a pair of strings   and  , define a distinguishing extension to be a string   such that exactly one of the two strings   and   belongs to  . Define a relation   on strings as   if there is no distinguishing extension for   and  . It is easy to show that   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   is regular if and only if   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  . Furthermore, every minimal DFA for the language is isomorphic to the canonical one (Hopcroft & Ullman 1979).

Myhill, Nerode (1957) — (1)   is regular if and only if   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  .

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

Let each equivalence class   correspond to a state, and let state transitions be   for each  . Let the starting state be  , and the accepting states be   where  .

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   relation as Nerode congruence,[1][2] in honor of Anil Nerode.

Proof

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

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

Construct the following equivalence relation:   if and only if   end up on the same state when running through  .

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

Now this gives us a bijection between states of   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.

Use and consequences

edit

The Myhill–Nerode theorem may be used to show that a language   is regular by proving that the number of equivalence classes of   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 the empty string,   (or  ),  , and   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   the relation   has infinitely many equivalence classes, it is not regular. It is this corollary that is frequently used to prove that a language is not regular.

Generalizations

edit

The Myhill–Nerode theorem can be generalized to tree automata.[3]

See also

edit

References

edit
  1. ^ Brzozowski, Janusz; Szykuła, Marek; Ye, Yuli (2018), "Syntactic Complexity of Regular Ideals", Theory of Computing Systems, 62 (5): 1175–1202, doi:10.1007/s00224-017-9803-8, hdl:10012/12499, S2CID 2238325
  2. ^ Crochemore, Maxime; et al. (2009), "From Nerode's congruence to suffix automata with mismatches", Theoretical Computer Science, 410 (37): 3471–3480, doi:10.1016/j.tcs.2009.03.011, S2CID 14277204
  3. ^ Hubert Comon; Max Dauchet; Rémi Gilleron; Florent Jacquemard; Denis Lugiez; Christoph Löding; Sophie Tison; Marc Tommasi (Oct 2021). Tree Automata Techniques and Applications (TATA). Here: Sect. 1.5, p.35-36.

Further reading

edit