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

Question

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.

My answer so far:

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

Thank you for your time.

Answer 1

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.

Answer 2

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.