Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.