1
$\begingroup$

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

  • 1
    Whatyou want to know if that set is a context-f$r$ee *language*: you should edit your title so that it asks the correct question.2011-10-30

1 Answers 1

3

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.

  • 0
    @user8250: yes, and we can confirm this with the same $p$roof. ≥ i$s$ a more general case.2011-10-30