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 |

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.

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

Re: Q3 2006 May 07, 2011 10:45AM |
Registered: 9 years ago Posts: 269 Rating: 0 |

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 sub**string**.

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 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 sub

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 |

Re: Q3 2006 May 07, 2011 04:40PM |
Registered: 10 years ago Posts: 3,496 Rating: 1 |

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^{2}xy^{2}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.

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

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

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 + uv^{2}xy^{2}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.

If len(w) > p then uvxyz + uv

(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

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.