# Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma

I have the following alphabet: $$Σ = {0, 1, . . . , 9}$$

and the Language $$L$$ defined as: $$L = \{ abc | a + b = c\}$$

where substrings $$a$$, $$b$$ and $$c$$ are interpreted as ordinary integers.

Assume $$L$$ is context-free. Then the pumping lemma for context-free languages applies to $$L$$.

Let $$n$$ be the the constant given by the pumping lemma.

Let $$z=10^n20^n30^n$$ clearly $$z \in L$$ and $$|z| \geq n$$

By the lemma we know that $$z = uvwxy$$ with $$|vwx| \leq n$$ and $$|vx| \geq 1$$

There exists possibilities...

My questions:

I can see 8 possibilities where $$vwx$$ can be within $$z$$. For example in the beginning including the 1 and overlapping with the initial $$0^n$$. Another example the initial $$0^n$$. Is this one way to think in this particular question? How can I pump and show that the result does not belong to $$L$$?

Suppose that $$L$$ were context-free. Then $$L \cap 10^*20^*30^*$$ would also be context-free. What is this language? It is easy to see that each of $$a,b,c$$ needs to contain a non-zero digit. Therefore $$a = 10^i$$, $$b = 0^j20^k$$, and $$c=0^\ell30^m$$. Clearly $$i=k=m$$, and so $$L \cap 10^*20^*30^* = \{10^{i+j}20^{i+\ell}30^i : i,j,\ell \geq 0\} = \{10^i20^j30^k : i,j \geq k\}.$$

To make our life easier, let us consider instances with more structure: $$L \cap 30^*130^*160^*2$$. Consider any word $$30^i130^j160^k2$$. The only way in which $$a+b$$ ends with $$2$$ is if $$a,b$$ end with $$1$$, and so $$a=30^i1$$, $$b=30^j1$$, $$c=60^j2$$. This shows that $$L' \triangleq L \cap 30^*1 30^*1 60^*2 = \{ 30^i130^i160^i2 : i \geq 0\}.$$ If $$L$$ were context-free, so would $$L'$$ be. Now define a homomorphism $$h$$ which maps $$1,2,3,6$$ to themselves and $$a,b,c$$ to $$0$$. Clearly $$L'' \triangleq h^{-1}(L') \cap 3a^*13b^*16c^*2 = \{3a^i13b^i16c^i2 : i \geq 0\}.$$ If $$L'$$ were context-free so would $$L''$$ be. Finally, define a homomorphism $$k$$ which erases $$1,2,3,6$$ and fixes $$a,b,c$$. Then the following language would also be context-free: $$k(L'') = \{ a^i b^i c^i : i \geq 0 \}.$$ However, this language is well-known to be non-context-free.

If for some reason you want to prove that $$L$$ is not context-free using the pumping lemma (the only reason I can see is that you were given this as an exercise), then you could consider instances of the form $$30^n130^n160^n2$$, which might be easier to handle than your original suggestion.

### Outline of a solution

Assume for the sake of contradiction, $$L$$ is context-free. Since $$1^*2^*33^*$$ is regular, $$M=L\cap 1^*2^*33^*$$ is context-free. Assuming the pumping length of $$M$$ is $$p$$, We can show that $$M$$ does not satisfy the pumping lemma by inspecting $$1^p2^p3^p$$. This contradiction shows that $$M$$ is not context-free.

### What is $$M$$?

Claim. $$M= \{ 1^i 2^{i+2d} 3^i : i\ge1, d\ge0 \}$$
Proof: Let $$1^i2^j3^k=abc\in M$$, where $$k\ge1$$ and $$a+b=c$$ as ordinary numbers.
The sum of the last digit of $$a$$ and the last digit of $$b$$ is the last digit of c, 3. So the last digit of $$b$$ must be 2. \begin{aligned} & &\phantom{22\cdots2}11\cdots1 &\quad(a)\\ &+&22\cdots222\cdots2 &\quad(b)\\\hline & &22\cdots233\cdots3 &\quad(c) \end{aligned} Each 3 in $$c$$ must be the sum of a digit of $$a$$ and a digit of $$b$$, one of which must be 1 and the other must be 2. So $$a$$ must be contain all $$i$$ 1's and no 2. The number of 1s, $$i$$ must be the same as the number of 3s, $$k$$.

### $$M$$ is not pumpable as in the pumping lemma

Let $$p$$ be the pumping length of $$M$$. Consider $$1^p2^p3^p=uvwxy$$, where $$|vwx|\le p$$, and $$|vx|\ge1$$.

• Suppose there is a 2 in $$vx$$. Since $$|vwx|\le p$$, $$vx$$ cannot have both 1 and 3.
• There is no 1 in $$vx$$. There are more 1s than 2s in $$uxw=uv^0wx^0y$$.
• There is no 3 in $$vx$$. There are more 3s than 2s in $$uxw=uv^0wx^0y$$.
• Suppose there is no 2 in $$vx$$.
• There is a 1 in $$vx$$. There are more 1s than 2s in $$uv^2wx^2y$$
• There is a 3 in $$vx$$. There are more 3s than 2s in $$uv^2wx^2y$$

So in all cases, we can pump $$1^p2^p3^p$$ into a word that is not in $$M$$.

### Exercises

Exercise 1. Try pumping $$1^p2^p3^p$$ directly to outside of $$L$$ (instead of $$M$$).

Exercise 2. Let $$\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$$ and language $$\text{SUM} = \{ abc\in\Sigma^* \mid a + c = b\}$$ where substrings $$a$$, $$b$$ and $$c$$ in the equality are interpreted as ordinary integers. Show that $$\text{SUM}$$ is not context free.

Exercise 3. Let $$\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$$ and language $$\text{DOUBLE} = \{ abc\in\Sigma^* \mid 2 \times a = b\}$$ where substrings $$a$$ and $$b$$ in the equality are interpreted as ordinary integers. Show that $$\text{DOUBLE}$$ is not context free.