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?

Tyndall

This should be on cstheory.stackexchange.com. – Changteh

@Jason: I think this question is off topic over there -- it's already been posted and closed. – Staffard

One suggestion: tell us what you're really trying to do. You're talking about doing some manipulations but not what you're trying to accomplish with them. – Undulatory

It turns out that my answer was fatally flawed -- you should probably unaccept my answer and choose William's instead. – Staffard

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.

Petry

The way that the pumping lemma is used for proving that a language is not context-free (and this language is not context-free!) is by picking any one string that is in the language, and showing that that string fails to pump. As for m: by assuming the language is context-free, you necessarily also assume the Pumping Lemma applies to it. The lemma states that m exists. You simply use m, and then derive the contradiction indicating that the original assumption (that the language is context-free) is wrong. – Petry

I should clarify in that first sentence: "... any one string of length greater than or equal to the pumping length m ..." – Petry

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.

Staffard

For both pumping lemmas, you can't pick how z is broken down. You can only construct z so as to impose certain conditions on how the breakdown can possibly occur. (This was one of the primary stumbling blocks for my tutees.) – Petry

@William: Here, I'm arguing that the language does indeed "pump", which only requires a single workable decomposition for sufficiently long strings, as opposed to a proof that all decompositions fail to pump (the more usual case). – Staffard

This language does not pump. A single workable decomposition of a single string defined by the pumping length does not imply that all decompositions pump, and all decompositions must pump for all sufficiently long strings in order for the language to satisfy the pumping lemma. (If still in doubt, see my update, I added the last three cases.) – Petry

@William: ".._all_ decompositions must pump..." is incorrect. Find a formal statement of the CFL pumping lemma (e.g. Hopcroft and Ullman), and pay close attention to the quantifiers. If some representation s = uvwxy exists with the required properties for each sufficiently long s, the conditions of the CFL pumping lemma are met. – Staffard

You're right, I was a bit quick on the keyboard and inverted quantifiers. Sorry for that, and thanks for pointing it out. Nonetheless, this language does not pump. See the string chosen in my proof (as well as the proof itself). The string is in the language, is sufficiently long, and does not pump in any decomposition. – Petry

@William: I see my mistake now -- I wasn't considering the n=0 case, where characters are being deleted rather than inserted, so there's indeed no choice of uvwxy that works for both n=0 and n>1. I'll update my answer accordingly -- thanks for hanging in there! – Staffard

Answer 3

The pumping lemma says that if a language is context-free, then it "pumps". That is, if it's context free, then:

There is some minimal length p, so that any string s of length p or longer can be rewritten s=uvxyz, where the u and y terms can be repeated in place any number of times (including zero).

A typical use is to demonstrate that a language does not pump, in order to prove that it is not context free. From your work it looks like this is what you're trying to do.

But the converse of the pumping lemma is false: There are languages which pump but are not context-free. In fact, your language is just such a beast. In other words, your language is not context free, but it does pump. (The easiest way to prove this is split s so that v="a" and y="b".) Therefore the pumping lemma is not likely to be useful to you in the analysis of this language. You may wish to consider Ogden's lemma instead.

Liberty

This language does not pump. As demonstrated above, the pumping lemma can be used to show it is not context-free. – Petry