3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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