0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rick Decker Jan 27 '17 at 18:17
  • $\begingroup$ 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) $\endgroup$ – Hendrik Jan Jan 27 '17 at 19:48
0
$\begingroup$

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

And yes, I think yours is just another correct pick.

$\endgroup$
  • $\begingroup$ Thank you for your answer! Also, I don't think an incorrect formatted equation is a member of the language anyway, as it does not meet the requirements to be in the language. $\endgroup$ – CPUFry Jan 27 '17 at 18:26

Your Answer

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

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