Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
+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
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.