$ADD = {x=y+z}$ with $x, y, z$ binary integers, and $x$ is the sum of $y$ and $z$. Pumping lemma to show that $ADD$ is not regular

Consider the alphabet $\Sigma = \{0, 1, +, =\}$ and the language $ADD = \{x=y+z|x,y$ are binary integers $x$ is the sum of $y$ and $z$ $\}$.

This is the (informal) solution I came up with (not sure about its correctness). Using the pumping lemma:

Take $s= 1^p=0+1^p$, $s \in ADD$. $s$ can be divided into three parts so that $s=xyz.$ The pumping lemma says that $|xy| \leq p$ and $|y| > 0$ so $y$ must be in the first $p$ $1's$. Choose $i=0$. Then the equation is false, so the languge $ADD$ is not regular. $\square$

Even though I think this is correct, in the answers they use the string $1^p=10^{p-1}+1^{p-1}$ which is also a correct pick, is mine just another correct pick?

• Yes. In general, there are often many choices for the string to be pumped, some better than others. In this case I prefer your answer to the other. – Rick Decker Jan 27 '17 at 18:17
• Your choice is a good one when showing the language is not regular: simple, just enough for the task. The alternative can be used when proving ADD is not context-free either (using a pumping lemma for context-free languages) – Hendrik Jan Jan 27 '17 at 19:48

Your answer has a slight omission: If perchance $y$ is of length $p$ (note: $x$ is permitted to be empty), then choosing $i=0$ leaves one with, not a false equation, but no equation (the string begins with '='). But of course the conclusion is the same. You can avoid that nit by choosing $i=2$ (say) instead of $i=0$.