# Q3 2006

Posted by BlaXpydo
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Q3 2006 May 07, 2011 10:10AM Registered: 9 years ago Posts: 269 Rating: 0
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
 Re: Q3 2006 May 07, 2011 10:32AM Registered: 10 years ago Posts: 3,496 Rating: 1
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.
 Re: Q3 2006 May 07, 2011 10:45AM Registered: 9 years ago Posts: 269 Rating: 0
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
 Re: Q3 2006 May 07, 2011 01:06PM Registered: 10 years ago Posts: 3,496 Rating: 1
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?
 Re: Q3 2006 May 07, 2011 04:13PM Registered: 9 years ago Posts: 269 Rating: 0
But how would you answer the question, given that it is 12 marks?

_______________________________________
Don't be different...be the one making a difference
 Re: Q3 2006 May 07, 2011 04:40PM Registered: 10 years ago Posts: 3,496 Rating: 1
Set n = 2p
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 = 2p) 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 uv2xy2z is in the language by assumption. In other words as far as the LHS of the word goes we must have a2p 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.
 Re: Q3 2006 May 07, 2011 06:26PM Registered: 10 years ago Posts: 3,496 Rating: 1
What do you get without length?

If len(w) > p then uvxyz + uv2xy2v

(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 > 2p.

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.
Sorry, only registered users may post in this forum.