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

  • 0
    +1 for remembering Myhill-Nerode rather than reflexively reaching for the (harder to apply and much less intuitive) pumping lemma.2012-10-16
  • 0
    @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.2012-10-16
  • 0
    @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.2012-10-16
  • 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.