This question already has an answer here:

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


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.

  • $\begingroup$ 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? $\endgroup$ – Kenenbek Arzymatov Apr 15 '18 at 12:13
  • $\begingroup$ There are many ways to proceed. I trust you. $\endgroup$ – Yuval Filmus Apr 15 '18 at 12:19

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