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$


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.

  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus May 26 '19 at 7:06
  • $\begingroup$ @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? $\endgroup$ – glockm15 May 26 '19 at 7:16
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 26 '19 at 7:25
  • $\begingroup$ @YuvalFilmus, I have updated my question. Am I on right track? $\endgroup$ – glockm15 May 26 '19 at 7:26
  • 1
    $\begingroup$ @glockm15 This answer that explains the common mistakes about using pumping lemma might help you. $\endgroup$ – John L. May 26 '19 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.