# Proving that language is regular or not [duplicate]

How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not:

$\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$

I started with the pumping lemma:

1. |$y$| ≥ 1
2. |$xy$| ≤ $p$
3. for all $i$ ≥ 0, $xy^iz$ ∈ $L$

But I don't know what to do next. How can split "$a+b=c$" string to start with the pumping lemma? Or I should apply another method?

## marked as duplicate by Raphael♦Apr 15 '18 at 19:31

The easiest way is to take the intersection of your language with $1^*+0=1^*$, which is $$\{ 1^n+0=1^n : n \geq 0 \}.$$ A similar option is to intersect with $1^*+1=10^*$, which gives $$\{ 1^n+1 = 10^n : n \geq 0 \}.$$ I'll let you finish the argument.
• So, I will get a contradiction when I will pump up? Because $1^{p+k}+0 \neq 1^p$ is not from that language, where $k$ is the |y|. Is it correct? – Roma Karageorgievich Apr 15 '18 at 12:13