# Proving a language is not a CFL although it can be pumped

Let $L=\{a^mb^nc^k\mid k\le \min(m,n)\}$

$L$ can be pumped with the pumping lemma for Context Free Languages which makes it very difficult to prove it is not a Context Free Language.

Any idea how to prove such a tricky case?

This is homework of course.

-
Can you show your attempt at applying the pumping lemma to L? It seems like the pumping lemma would work - note that the pumping lemma allows characters to be pumped zero times as well. –  donburi Jan 14 '13 at 21:05
I know it will work, that is the tricky part because the easy way to prove a language is not a CFL is contradict the pumping lemma which can't be done it that case. –  Yoni Hassin Jan 14 '13 at 21:10
@donburi I don't think pummping zero times will work. Since you have $vxy$ you can always make $v=a \text{ or }b$ and $y=c$, in which case pumping zero times can't change anything. –  JSchlather Jan 14 '13 at 21:37
After further reading i realized it has to proven with Ogden's lemma. Still working on that.. –  Yoni Hassin Jan 14 '13 at 23:28

Hint: Suppose L is regular and the pumping length is $n$, then consider the string $w = a^{n}b^{n}c^{n} \in L$. By the pumping lemma, there exists a decomposition $w = uvxyz$ such that $\left|vxy\right| \leq n$ (and $\left|vy\right| \gt 0$) and $uv^ixy^iz \in L$ for all $i \in \{0, 1, 2, \ldots\}$. What are the possibilities for $vxy$?
Are we speaking about the pumping lemma for CFL's? Because $vxy$ can be $a^tb^s$,$t+s \le n$ so $w$ can be pumped and nothing can be proved here, i am wrong? –  Yoni Hassin Jan 14 '13 at 23:45
Suppose $vxy$ were $a^tb^s, t + s \leq n$. Then what is $uv^0xy^0z$? –  donburi Jan 15 '13 at 0:02
$a^{n-t}b^{n-s}c^n$ ? And using the fact that $t+s>0$ proves the whole thing? Actually you claim that $L$ can not be pumped for any partition of $w=uv^ixy^iz$ ? –  Yoni Hassin Jan 15 '13 at 9:13
You still have to check all the other possibilities: $vxy$ is all $a$, all $b$, or all $c$, or is $b^tc^{n-t}$, but it's not too difficult to show that they don't work either. –  donburi Jan 15 '13 at 18:03