Q3 2006

On the word we choose for this pumping lemma (n = 2^p), and we use the case solution, do we still get 5 parts? or 4?

_______________________________________
Don't be different...be the one making a difference

You deliberately pick a word that's big enough to have 5 parts.

The way you ensure that is that you have eg. a power of 2p symbols (could be wrong here, actually busy fixing up my poor old aunty's messed up email at the moment so need to be even more careless than usual).

Once your word is big enough (and only if it's big enough) then if it was generated by a CFG, it must have 5 parts.

Your word could perhaps have 4 parts. If it does, it's not a word generated by a CFG, though.

Usually you're trying to prove that G is not a CFG or some negative like that, so a 4 part word would make you very happy. Goal achieved. The word fails, so then G fails. Negative proven.

But does not the terminal 'b' between the 2 a's make it impossible to have 5 cases?

How did you do that?

_______________________________________
Don't be different...be the one making a difference

That would make a nice short answer, I think (without going into why - just intuitively).

But that's the point, isn't it?

You want to show that L is not a CFL. You demonstrate that it does not pump. You're done.

Or are you saying there's no way to make up 5 part words from this language? If that's what you're doing you're getting your uvxyz meaning wrong. Each of those is a substring.

So if you can make a 5 letter word with some choice of n, you can make a "5 part word".

Or am I missing your point?

But how would you answer the question, given that it is 12 marks?

_______________________________________
Don't be different...be the one making a difference

Set n = 2^p
This guarantees that w is long enough for the theorem to apply.

Now try to prove that "This language is a CFL" leads to a contradiction.

Taking the given of the assumption, it "is so" that w divides up into uvxyz

We take every possible way this w (having n = 2^p) could divide in such a way that the output of pumping it is substantially different.

Maybe start in the middle of the word? What x shall we have? Try just the middle b as an x? (Since one can make the observation that every word in this language must have the substring aba somewhere in the middle, so we can't go adding b's to words of this language).

If just b is our x (or maybe even the aba would do) then uv is a bunch of a's followed by a bunch of a's. Maybe take just one a, and see if we can get an exception out of it? (Little warning bells are screaming at this time, but I'll just blunder on - Just to let you know that if you think I am on the right track, I actually suspect I'm entering the wrong track here).

Now the word uv²xy²z is in the language by assumption. In other words as far as the LHS of the word goes we must have a^2p aab...something. I mean this must also be a word of L.

Now that will be no problem if we can devise a RHS which preserves all its proportions.

Looking to the right of "middle b" we have to provide one extra a to have enough a's. We also need to provide another b. And there would appear to be a problem with that.

You can't make a pumped word part of this language. And if you can't do that, it's not a CFL. But we assumed it was. Contradiction. Assumption is wrong. Zap.

if you correct this explanation you'll probably know exactly how to do the pumping lemma.

What do you get without length?

If len(w) > p then uvxyz + uv²xy²v

(Call that the "practical definition" if you want).

If you can show that none of the million possible uvxyz arrangements pump, you're done.

======

What extra do you get with length?

The middle piece has a minimum length.

vxy > 2^p.

So you can pick a w who's middle you're reasonably sure of?

======

I think you'd have to go further toward fixing the "explanation" than that to get home and dry, but it is a start.