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

$$\{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!

## 1 Answer

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.