[Math] Showing that a language is not regular using Myhill-Nerode Theorem

computer scienceregular-language

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

Thanks in advance.

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$}\}$.

Best Answer

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.