3
$\begingroup$

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

  • 1
    @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.)2012-10-16

1 Answers 1

3

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.