Show that $L=\{a^i b^j c^k\,:\, i < j < k\}$ is not context free

Question

I am looking to show that $L=\{a^i b^j c^k\,:\, i < j < k\}$ is not context free.

So I suppose that it is a context free language and use the pumping lemma. Let $n$ be the parameter of the lemma and define $z=a^nb^{n+1}c^{n+2}$. We can so write $z=uvwxy$ with $|vwx| \leq n$ and $|vx|\geq 1$. Now we look at different cases and there I got stucked at $2$. These are the following:

1. $vwx$ is $b^qc^q$ for $p+q \leq n,\, p+q \geq 1$
2. $vwx$ is $c^p$ for $p \leq n, \, p \geq 1$

The idea should be that for all $i \geq 0$ $uv^iwx^iy \in L$. Now for $i=0$ we should get a contradiction but I don't see where. Can someone helps me out?

Answer 1

For $z = a^n b^{n+1} c^{n+2}$,

• For your case 1: either $v$ or $x$ must start with atleast one $b$ (i.e. $v=bb^*c^*$ or $x=bb^* c^*$). If $i = 0$, the new string will have its $b$s reduced by at least 1. Hence, the new string would be $a^n b^r c^s$ where $r\le (n+1)-1=n$. With that, the new string is not in $L$.

• For your case 2: If $i = 0$, the new string will have its $c$s reduced by at least 1 (i.e. either $v$ or $x$ can be empty, but not both). Hence, the new string would be $a^n b^{n+1} c^{r}$ where $r\le (n+2)-1=n+1$. With that, the new string is not in $L$.