Pumping Again

Trying for bare bones here, now.
==========

P = "G is CFG .AND. w is in G with len(w) > 2^p"
Briefer form of P: "If (ANY) w is long enough ..."

Q = "w must split somehow into uvxyz PLUS uv²xy²z must also be in G"
Briefer form of Q: "then w pumps."

Theorem's form: P -> Q

Equivalent to this is the contrapositive: ~Q -> ~P

That means you can take w -fails-Q and conclude ~P. You can prove a NEGATIVE.

===========

Now I get a bit tangled up on what we have to do to w sometimes, and I think I may be onto why. It's because you prove that one word is an exception to Q. This one single chosen word doesn't pump, and since the theorem says every word must pump, you've supplied the necessary "exists" to refute that "forall".

Great. But then you go about this "exists" proof in a sort of "forall" kind of way. You only need to find one exception, but to find that exception the (one) word you reckon will fail must fail no matter what arrangement you try. That's what I mean in a Kind Of "forall" way. You have to cover Every possibility.

You're trying to prove a single "exception to the rule", but you have to do that by covering all the cases.

Put that way, there's nothing particularly difficult about it. Maybe when a bit of this kind of confusion kicks in just remember "all-cases is not all-words".

The "forall" is an illusion. It's only KindOf ...

========

The with-length version of the theorem is easier. All it does is give you more ways of proving your exception.

I can make that simpler for the exam room, I think.

Given w longer than 2^p if G is a CFG w is forced to be uvxyz.

Take a specific w. There will be a limited number of patterns it can have as a uvxyz. (Make sure to pick one with as few options as possible.)

For any of the uvxyz you can think of for that one carefully selected w, show that uv²xy²z doesn't follow.

====== There endeth the Pumping Lemma Without Length. Your weeping is noted. 2 marks will be deducted for wetting the paper like that.

If they're feeling cruel and want to watch the tears well up in your eyes as hope slips away, they'll ask for the Pumping Lemma Without Length; If they're feeling benevolent and warm and are quietly willing you on to success as you write, they'll give you the pumping lemma With Length.

With Length is Good. If you see it, rejoice a little first before you go on.

=======
Pumping Lemma with Length gives you everything the other one gives you, plus: The Middle Bit has a maximum size.

vxy <= 2^p

This means if you pick w to be big enough (>2^p) but not too big, you can be sure of a minimum size vxy. That minimum size is going to force it to be of a certain configuration....

Er... in fact maybe your w can't ever be too big now? Make w big enough so that vxy has at most 2 groups of a's/ b's.

What do you think? Bigger is better? Or must we try to cut this to some "right size" between too big and too small?

Given a certain amount of roughness, the above would appear to be pretty much correct. See p19 of TL102, particularly point 2 and 3 near the top.

You set up one (specific) word to fail.

You fail that word by showing there's no way it could succeed. (Several cases to cover).