$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

cs.stackexchange https://cs.stackexchange.com/questions/69393

Pergunta

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?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top