Show that $\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language by using pumping lemma

Question

$\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language.

I attempted to try this, but I keep on getting stuck. I was planning on solving it like a pumping lemma question for grammar, but I am not sure.

Thank you!

Answer 1

The pumping lemma gives a necessary condition for a language to be a CFL, so a common way to show that a language is not a CFL is to show that the pumping lemma's condition is not satisfied. However, the language given $\textbf{does}$ satisfy the required condition, so the pumping lemma tells us nothing about the language.

Let $L=\{a^ib^jc^k | i>j>k>0\}$ and let the pumping length $p=1$ (there are no strings in $L$ of length less then $6$ except the empty string, so this is really the same thing as $p=6$). For a string $s=uvwxy$, let $v=a$ and let $w,x$ be the empty strings. Each string in $L$ starts with an $a$, so we can write $s=uvwxy$ where $u,w,x$ are the empty string, $v$ is $a$ and $y$ is the rest of the string. This satisfies the conditions of the pumping lemma:

• $|vwx|=|a|=1\le 1=p \implies |vwx|\le p$
• $|vx|=|a|=1 \implies |vx|\ge 1$
• $uv^nwx^ny=v^ny=a^ny=a^{n-1}s\in L\implies uv^nwx^ny\in L$ for all $n\ge 0$

Therefore, it is not possible to show that $L$ is not a CFL using the pumping lemma.