Editing Myhill–Nerode theorem (section)

==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 two binary strings <math>x, y</math>, extending them by one digit gives <math>2x + b, 2y + b</math>, so <math>2x + b \equiv 2y + b \mod 3 </math> iff <math>x \equiv y \mod 3 </math>. Thus, <math>00</math> (or <math>11</math>), <math>01</math>, and <math>10</math> 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 <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.