Is $L=\{a^{i}b^{j}c^{k}\mid i\geq j\geq k\} $ a context-free language

Question

The given language is $ L = \{ a^{i} b^{j} c^{k} \mid i \geq j \geq k \} $

If yes can someone give its productions because I have tried a lot ....

The problem of course is to limit the value of b ....

I have tried to apply the pumping lemma for context-free grammar and I think it does satisfy it... Can someone verify this...

Thanks a lot ..

PS :- It is not a homework...

Answer 1

It is indeed not a context free language.

Pick $z = a^{p}b^pc^p$

$vwx$ cannot contain a's, b's and c's. We pump the string depending on the string $vwx$ as follows:

1. There are no c's. Then we try pumping down to obtain the string $uv^0wx^0y$ to get $uwy$. This contains the same number of c's, but fewer a's or b's. Therefore it is not in $L$.

2. There are no b's but there are c's. Then we pump up to obtain the string $uv^2wx^2y$ to give us more c's than b's and this is not in $L$.

3. There are no b's but there are a's. Then we pump down to obtain the string $uwy$. This string contains the same number of b's but fewer c's, therefore this is not in $L$.

4. There are no a's. Then we pump up to obtain the string $uv^2wx^2y$ to give us more b's or more a's than there are c's, so this is not in $L$.

Since we can come up with a contradiction for any case, this language is not a CF language.