patternMinor
Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma
Viewed 0 times
freeprovepumpingusinglemmacontextabcnot
Problem
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.
$Σ = {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.
Solution
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.
$$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.
Context
StackExchange Computer Science Q#109195, answer score: 3
Revisions (0)
No revisions yet.