# Showing that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that?

Let $Σ = \{0, 1, +, =\}$ and

$\mathrm{ADD} = \{x = y + z \mid x, y, z \text{ are binary integers, and$x$is the sum of$y$and$z$}\}$.

-
+1 for remembering Myhill-Nerode rather than reflexively reaching for the (harder to apply and much less intuitive) pumping lemma. – Henning Makholm Oct 16 '12 at 16:40
@Henning: I’ll give you harder to apply, at least in many cases, but I think that the pumping lemma is more intuitive than M-N. – Brian M. Scott Oct 16 '12 at 18:47
@Brian: Perhaps it's just me, but I can never even remember how the pumping lemma goes. In contrast Myhill-Nerode is plain, simple and direct: How many different states does an automaton that recognizes this language need in order to remember all relevant information about the part of the string it has already seen? If that number is infinite, the language is not regular. – Henning Makholm Oct 16 '12 at 19:20
@Henning: But the pumping lemma is just the pigeonhole principle: if there are $n$ states, and $|w|\ge n$, $w$ causes the machine to visit some state twice, and that gives you a loop that can be inserted as many times as you like. (I’m always fascinated by how diverse people’s notions of natural and intuitive can be.) – Brian M. Scott Oct 16 '12 at 19:29

Myhill-Nerode tells us, that a language $L$ is regular iff its Myhill-Nerode-Relation $\equiv_L$ given by
$x \equiv_L y :\!\iff \forall z \in \Sigma^*: xz \in L \leftrightarrow yz \in L$ has finitely many equivalence classes.
So to prove that our language $\mathrm{ADD}$ isn't regular we have to give an infinite set of pairwise inequivalent words. For $n \in \mathbb N$ let $x_n = 10^n \in \Sigma^*$. Then $\{x_n \mid n \in \mathbb N\}$ is an infinite set of words, we will now show that they are pairwise $\equiv_{\mathrm{ADD}}$-inequivalent. So let $n \ne m$, for $z_n = \mathord{+}0\mathord=10^n$ we have $x_nz_n = 10^n\mathord+0\mathord=10^n \in \mathrm{ADD}$, but $x_mz_n = 10^m\mathord+0\mathord=10^n \not\in \mathrm{ADD}$, so $x_n \not\equiv_{\mathrm{ADD}} x_m$ and hence $\mathrm{ADD}$ isn't regular.