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

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...

-
Whatyou want to know if that set is a context-free language: you should edit your title so that it asks the correct question. –  Mariano Suárez-Alvarez Oct 30 '11 at 20:57

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.

-
Note: I am presuming that $k \geq 0$ –  user12205 Oct 30 '11 at 21:11
Yes that is true ... One follow up doubt though ... If I have something like i > j > k would it still not be a CFL ? –  user8250 Oct 30 '11 at 21:20
@user8250: yes, and we can confirm this with the same proof. ≥ is a more general case. –  user12205 Oct 30 '11 at 21:33