Pumping Lemma with Context Free Languages

Question

I have the language {a^i b^j c^k | i,j,k>=0 & i>j & j>k} I began by assuming some m is picked for me, such that a string

   z = a^m b^(m-1) c^(m-2)

Then the string is split up into (z =) uvwxy so that vx are not empty and #(vwx)<=m Then when I get to pick an "i" I get confused. Say I pick i=1 then I have: uv^1wx^1y and I'm not entirely sure where to go from that because to me it looks like I could pick a vwx that IS in the language.

Any suggestions?

Answer 1

I'd begin by picking a slightly better z = a^(m+2)b^(m+1)c^(m), where m is the pumping length. This string is clearly in the language and its length is greater than or equal to m. So, assuming the language is a CFL, the pumping lemma applies to it. Now, since you know that |vwx| <= m and that |vx| > 0, you also know that vwx must consist of (1) only a's, (2) some a's and some b's, (3) only b's, (4) some b's and some c's, or (5) only c's.

Deal with each case individually. I'll do the first two cases for you.

Case 1: This means that vx is a^(s) for some s > 0, since the lemma tells us |vx| > 0. Now suppose you take i = 0. Then the lemma tells us that z' = uv^(0)wx^(0)y should still belong to the language. However, z' is of the form a^(m+2-s)b^(m+1)c^(m) and, since s > 0, violates the condition that the number of a's must be strictly greater than the number of b's. Thus z' is not in the language, and this case fails to pump.

Case 2: This means that vx is a^(s)b^(t) for some s,t such that s+t > 0. Suppose, again, you take i = 0. Then z' is of the form a^(m+2-s)b^(m+1-t)c^(m). If t is positive, then the condition that the number of b's be strictly greater than the number of c's is violated. If t is zero, s must be positive, in which case we degenerate to case 1. Thus z' is not in the language, and this case fails to pump.

For dealing with the other cases, remember that you can pick a different pumping exponent i for each one.

Edit: (From past discussion on this question, I had decided to show the other three cases.)

Case 3: This means that vx is b^(s) for some s > 0. Take i = 0. Then z' is of the form a^(m+2)b^(m+1-s)c^(m). Since s is positive, this violates the condition that the number of b's be strictly greater than the number of c's. So z' is not in the language and this case fails to pump. (You could also take i equal to anything but 1 to show that this case fails to pump.)

Case 4: This means that vx is b^(s)c^(t) for some s,t such that s+t > 0. Take i = 2. Then z' is of the form a^(m+2)b^(m+1+s)c^(m+t). If s is nonzero, then the condition that the number of a's be strictly greater than the number of b's is violated. If s is zero, then t must be nonzero, in which case the condition that the number of b's be strictly greater than the number of c's is violated. So z' is not in the language and this case also fails to pump.

Case 5: This means that vx is c^(s) for some s > 0. Take i = 2. Then z' is of the form a^(m+2)b^(m+1)c^(m+s). Since s is positive, the condition that the number of b's be strictly greater than the number of c's is violated. So z' is not in the language and this case fails to pump.

Since all five cases fail to pump, the Pumping Lemma tells us that this language is not context-free.

Answer 2

Note: After a bit of back-and-forth in the comments, I see that I'm wrong and William's answer is actually correct. I'll leave this answer here so I can point out where my line of reasoning failed.

I'd think about it like this:

What properties must substrings v,w,x have in order to even have a chance of remaining within the language definition after pumping? Neither v nor x can contain substrings like "ab" or "bc", or else they immediately pump out of the input language. So each of v and x must be either empty, all a's, all b's, or all c's.

Consider the string aaabbc, which is in the language.

Now what happens if we pick u="aa", v = "a", w = epsilon, x = "b", y = "bc"; and pump v and x? (Here's my mistake: I didn't consider the n=0 case, where v and x are actually removed from the string; no matter how you choose uvwxy, the proof will fail for either the n=0 or n>1 case when uvwxy is pumped to uvⁿwxⁿy).

Note: The CFL pumping lemma can be used to prove that a language is not context-free, but obeying the pumping lemma in itself is not sufficient to show that a language is context-free. There are languages that are not CF, but all the conditions of the CFL pumping lemma still hold. For such cases, you might want to have a look at Ogden's lemma, a somewhat more powerful test, and see if that can be used to show that your language is not CF.