# Pumping lemma for regular languages confirmation

I have the language $$\Sigma = \{0,1,+,= \}$$ and $$\mathrm{ADD} = \{x = y + z \mid \text{x, y, z are binary integers and x is the sum of y and z}\}$$

And with the pumping lemma I find what a think is a counter example to the $$xy^iz \in \mathrm{ADD}$$ with $$i = 2$$, $$p = 4$$ and $$s = 0+1^p$$:

$$x = 0, y=+1, z= 111 \rightarrow 0+1+1111$$

Which becomes the addition of 3 binary integers so I would say that it does not belong in ADD and so the language is not regular. Or is it still regular cause I can just simplify things down to the addition of two binary integers, e.g 1+1111 or 0+10000

Update on comment from Yuval:

So if I can only assuming a P satisfy the lemma then with

s = $$0+1^p$$ can I still assume that say $$x=0$$,$$y=+1^p$$,$$z=\{\}$$?

Then again in general for any $$i \ge 0$$ we can have something in the form if $$i=2$$

$$0+1^p+1^p$$

which again is brings me back to my first question if that is still considered in ADD or not as it is addition of 3 binary integers.

• You don’t get to choose the decomposition of your word into $x,y,z$; you also don’t get to choose $p$. Using your method of “proof” you can easily “show” that $10^*$ is not regular (exercise). – Yuval Filmus May 26 '19 at 7:06
• @YuvalFilmus, if I can't choose p or the decomposition how would I divide the word into x, y and z to check one of the conditions of the lemma? – glockm15 May 26 '19 at 7:16
• You don’t. Given $p$, you choose a word; and given a decomposition, you choose $i$. I suggest taking a look at some worked examples and at relevant questions on this site. – Yuval Filmus May 26 '19 at 7:25
• @YuvalFilmus, I have updated my question. Am I on right track? – glockm15 May 26 '19 at 7:26
• @glockm15 This answer that explains the common mistakes about using pumping lemma might help you. – John L. May 26 '19 at 14:05