Welcome! Log In Create A New Profile

Advanced

Pumping Lemma Help

Posted by 35994908 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Pumping Lemma Help
April 08, 2011 02:11PM
Hi,

I am really struggling to come to an understanding of Pumping Lemma. Does anyone have a good resourse or extra notes that are easy to understand?

If so you could you either post the links or email me the notes at mighytybrad@gmail.com

Thanks!
Brad
avatar Re: Pumping Lemma Help
April 10, 2011 02:39PM
Your language is in CNF. That means all live productions are of the form X -> YZ.

That means you have two choices for any live production. That gives you a 2 ...

You have a finite number of these live productions. That number is called p.

At production S you're on 20 of these. For "each of those" there are 2 choices so that's 20 * 2 = 20+1 = 21 = 2. Putting it in "pattern form" we have 2n+1 possibilities in the next row, if n is the number of live productions in the current row.

The maximum n can be if you insist that all the productions in a row be unique is ?

No I don't suppose this would be especially helpful. Not unless I've just been lucky and hit the spot you're missing.

What would be helpful is if you would set out what you think you DO understand of this. Not all in one go. Just little by little. "By dialogue" we might all get to understanding it better, taking it from what you identify as the point of breakdown in your own understanding.

To me, Cohen explains it all pretty well. All you need to do is go through without undue haste. And if your problem is that you're in too much of a hurry then an alternative explanation is just going to make things worse. It's going to eat up even more of the little time you feel you have to spare.

In "operative terms", if your word is long enough (doubled and doubled as many times as you have live productions) it breaks into 5 pieces. You can just take that on faith if this is all you want to know. It breaks up into 5 pieces as long as it's long enough. From there on, among the additional words that appear in the language after this (as you build words one character longer than the minimum "long enough word"winking smiley will include "pumpings" of the word you had. They will pump back one of the substrings on either side of the middle, or both of these.

If some arbitrary word of sufficient length (which you could call q if you don't like the letter w) that meets the definition of your proposed CFG, fails to pump (to keep replicating some substring) then that word doesn't obey the rule the theorem says it must. And if an arbitrary word does this, then it follows that any word could. And if w doesn't pump then G can't be a CFG.

There you go. Crappy explanation. Pull it to pieces. Show where you think it's wrong (which helps the both of us), show where you think it might be heading in the right direction but is missing something. That should be enough to get some kind of discussion rolling. In the end you'll be explaining this to me. You'll see!

«edited»
avatar Re: Pumping Lemma Help
April 12, 2011 01:42AM
A shorter reply closer to what you asked for would be "Look at the tutorial letter". The "official proof" for the pumping lemma is in there, if it's the proof you're interested in.

As for the "dialogue approach", I'll give it one more go. My initial reply is imperfect (as I confessed at the time), and I would say it's downright defective when I start to talk about "all the productions in a row being unique". The idea of a dialogue would be that one of the many using Osprey for the course would say "Rubbish Eddie; it's like so", at which point I would say a grudging "Thank you".

To get the self embedding idea, note that you have a finite number of PRODUCTIONS (p of them).

Here's a picture of some of these:

Z -> XY
Z -> AB
Z -> YZ
X -> AA
...

A tree of productions used to produce some w would expand to double the "local" width every live production you used. If you pushed to maximum width as fast as possible you'd have to double and double, and not slow down to write letters along the way. (You should perhaps try to, and see what happens to your tree depth if you do, because the "depth" or "height" or "path length" is what matters in the end).

The basis of the pumping lemma theorem rests on the fact that if you go down to row p, you'll have a maximum (by always doubling everything) of 2p live productions there. Now taking the "horizontal view" the row could be XYXYXYXYXYXY...XY for all you care.

Note that I'm almost certain I've gone and mucked up my exact numbers again here, but don't worry too much about that. You'll get it nice and neat in the Study Guide.

The thing is that the next row down you can fill in dead productions to write w out, but you're still one letter short. Len(w) > p. Not Len(w) >= p.

Let's say the dead productions are something like X -> a | b | c | d and Y -> q |w | e | r |t |y just to give something concrete to fill in for that last row. (This is another way you can tackle it. Forget abstractions and write an actual word out).

OK so you write some kind of w using the dead productions (which are probably not correct either) and you have to put in one more live production to give "one letter for this row, and one more for the plus-one". That pushes you into row p+1 (the number is dead wrong here, but you can easily fix this detail up yourself).

The point is that if you go UP the tree, looking for PRODUCTIONS (they have two things on their RHS, right?) you're going to find that there's no way to have entirely unique productions all the way up any path through the tree. On any particular backtracking path you're going to find a production (a production) that is exactly the same as the one you're backtracking from, up in row p+1.

I'll draw a picture. Down at the bottom of the tree (typographically speaking) we have X -> AB and leading from those we have A -> a, B -> b.

Track up the tree, which you've tried your best to ensure no replications. No luck. You're going to find that production up there. You're going to find X -> AB. Not just plain X. Not just plain A or plain B. The whole thing. This is the beginning of wisdom, I've been told. There's more to follow, but first things first.

OK let me finish by trying to get those rows straight. The root is S, right? And it's "row zero" if you choose to see things that way. It has 20 symbols. Then you go down to "row p" in this counting scheme. Now since you're counting from zero in this scheme of things the actual number of rows you have is p + 1. And then the nonterminals in that row point at terminals in the next row. That brings the number of rows up to p+2, which is more than p.
avatar Re: Pumping Lemma Help
April 12, 2011 03:15PM
Skipping ahead from the proof of the existence of the self embedding nonterminal that results from doing all the above properly (and not in such a mangled way), first notice that although you use the fact that the entire production "down here" has to also be somewhere "back there", in fact the only objective of the proof is to show that there's at least one self-embedded non terminal.

Now what words are in L? Every single possible word, right?

And it's the productions that determine what words are possible, not so? "Production" is just a rather odd name for "rule".

So let's see ... coming back down the tree from that self embedded nonterminal you found, you get to exactly the same letter ... but what happened along the way? You used a long sequence of productions. That entire chain of productions takes you down to the letter at its "root". The whole kaboodle "flows from that root".

So then it's clear that you're allowed to have as a word in this L, X-blahblahblah-X-blahblahblah right?

If you were allowed to reach this repeated X you've found down here, then you're always allowed to reach it, aren't you?

If fact you're allowed to form the word having X-blahblahblah-X-blahblahblah-X-blahblahblah-X-blahblahblah-X-blahblahblah-X-blahblahblah-X-blahblahblah-X-blahblahblah- ... ad infinitum, right?

Another way of putting that is to say that those are all possible words of L.

And if a word is a possible word of L then it better be in L.

Notice how there's something like "pumping" going on there? Running a bit ahead, you could say "my uvxyz is uX-blahblahblah-x{lambda}z ... and you'd be pumping away merrily if the rules allowed this.

For instance you'd be able to produce u-X-blahblahblah-X-blahblahblah-x{lambda}z-x{lambda}z and so on.

Since those words are possible ...

And what's possible is mandatory ...
avatar Re: Pumping Lemma Help
April 13, 2011 12:09AM
Too verbose, then?

Cohen's algebraic proof on p363 is perhaps a better path to enlightenment, then.

P=*> uPz =*> uvPyz =*> uvxyz

Obviously the first P is the "upper P", and the next one (in friendly blue letters) is the self-embedded descendant of that ancestral P.

The only thing to note is that one must not mistake the lowercasishness of the variables for "dead productions". x , for instance is that huge chain of productions that fills in the gap between the upper and lower P - though of course at the leaf ends of these many million branches you finally fill the whole thing in with terminals at the very end of the production.

You should be able to keep sticking production-P, with its two legs, into the place of lowest nonterminal P again and again.

And if you're allowed to make a word that way, it's part of the language generated by the grammar. By being "permissible", it becomes "compulsory".

=========== subtopic 2 ============

Q: How would you use the pumping lemma? A: To show that some G is not a CFG.

Reduce the pumping lemma to P -> Q (as in formal logic). Here new-P stands for quite a few conjuncts that go on the "if" side of this proposition.

Now if you manage to prove ~Q what does that say about P?

That's the outer skeleton of how you're using the pumping lemma.

Or according to me I claim so.
Re: Pumping Lemma Help
April 15, 2011 10:37AM
Hi,

Thanks for all these posts!! I've quickly skimmed through them. I have had a busy week so I haven't had time to study. I will be going through it this weekend and then give some feedback.

Thanks again!
avatar Re: Pumping Lemma Help
April 15, 2011 12:13PM
No problem. Just trying to grasp it nice and firm, myself, too.

I'd better summarise a bit.

Number one tip is read the tutorial letter on the proof.

Number 2 tip would be Try the algebraic proof done in colour above, and found in Cohen p363.

I suppose if you've had a busy week that's a good thing really. Pity about the study side, but there are other things that matter more.
avatar
cev
Re: Pumping Lemma Help
April 16, 2011 12:59PM
I found a lecture on YouTube that explains pumping lemma. The lecture is broken down into 10 videos, which I am currently downloading, but from what I've seen in the first video it looks like it might be very helpfull.

Link to the first lecture :



Hope it helps.
avatar Re: Pumping Lemma Help
April 16, 2011 03:14PM
Excellent lecturer. This would certainly help with getting the idea of the FA version of the pumping lemma, which contains the basic idea of "pumping" and how to use it. That's quite a lot to have in hand right away.

The correct terminology for "how to use it" is : "Use the Contrapositive".

We have P -> Q proven in the pumping lemma theorem.

That is logically equivalent to (~Q -> ~P)

So you prove ~Q .. "Not:tongue sticking out smileyPumps" «edited»
That then eliminates the -> sign, leaving you with ~P .. "Not::CFG"

This, you get from this lecture, in clearer terms.

Off topic: My assignment result says "Take what ed has to say about this subject with a pinch of salt". It was shall we say "a slight disaster" - nothing utterly catastrophic, but defective, nonetheless.

Mind you I think I have admitted to be trying to figure it, rather than "showing the way" somewhere up there?
Sorry, only registered users may post in this forum.

Click here to login