# Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free?

I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\{a^ib^jc^k : i\leq j\leq k\}$. I can easily build a linear turing machine, that would delete a, b and c for each a and then b and c for each b and if the only thing left, will be c, then the word belongs to the language. So I know the language is context-sensitive. What I can't figure out is if the language is context-free.

I tried to build a pushdown automata but I couldn't find any. I also tried to use the pumping lemma but wasn't able to find a good word to prove it's not context-free. Could you help me?

• Okay so I will set n to p-1 therefor make sure that the vxy (w=uvxyz) contains max two letters. So if I get b's and c's it will work but if I get a's and b's I can easily get rid of them and the word will stll belong to the language. I could use i=high number and pump a's and b's and therefor find a word that has more a's and b's than c's which doesn't belong to the language. But I thought that the pumping lemma says I have to have one i for every splitting. Or can I find a different i for each splitting? Jan 2, 2017 at 13:36
• I didn't know that. Thank you so much. Should I check something to show that the question was answered? Jan 4, 2017 at 10:48
• At to moment you cannot accept, because this was only a comment. I will copy-paste this into an answer. Jan 4, 2017 at 11:26

A word like $a^nb^nc^n$ should work. Remember that the pumping lemma also allows you to pump down, i.e., delete the pumping segments.
Also, each splitting $z=uvxyz$ can have its own "contradiction" to show it does not adhere to the pumping lemma. You can use different arguments, so different $i$ for each splitting. That is very natural here as $a$ has the minimal number of occurrences, and contradiction is reached by adding occurrences, whereas for $c$ deletion (choosing $i=0$) will get you into trouble.