Welcome! Log In Create A New Profile


Pumping Lemma with length

Posted by jeanbodemer 
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 with length
November 17, 2007 10:33PM
I'm still need a bit of help with this. The example and assignment solutions aren't helping much as they are way too long and it's difficult to determine what is really required.

Does anyone have a few examples or maybe some advice on how to tackle these types of questions?
Re: Pumping Lemma with length
November 18, 2007 06:43PM
i also found too much waffle to keep my attention span so i summarised it, if you memorise this you can preety much use it for a PL question i reckon

- assume this lang is context free ..
...so there exists CFG with p live productions
...meaning we can apply PL with length
... meaning any word can be represented as uvxyz where length (vxy) =< 2p
... and uvnxynz is also in the language

-choose an appropriate word in the lang ( ok here you just replace any "n" you get in the questino with "2p) to try and pump eg if they give you anbnc2n-1 so say n=2p so

it becomes a2pb2pc2p-1

then you start waffling :
- supose vxy consists entirely of a's, but then according to the PL the word uvvxyyz is also in the lanuage , this will have more than 2p a's thoguh followed by b2pc2p-1.. and this isnt in the language

- repeat the above step using "entirely of b's , then again with c's to show how all those words cannot possibly be in the lanuage) at te end of it you concude that you cann't get it to work with the PL so it it not context free
Re: Pumping Lemma with length
November 18, 2007 06:57PM
Thank Iva! thumbs up
avatar Re: Pumping Lemma with length
November 18, 2007 06:58PM
thanks!!! grinning smiley
Re: Pumping Lemma with length
November 18, 2007 08:54PM
iva, you missed the cases where vxy can be a's and b's. Like, aaabbbb
Re: Pumping Lemma with length
November 18, 2007 09:15PM
sorry yes ,if the question is in the form anbn then you need that case of a mixture , when i was writing i was thinking of an example like anbncn
avatar Re: Pumping Lemma with length
November 19, 2007 01:39AM
just wrote, good luck guys (and gals, but we all know iva's gonna smash it winking smiley)
Sorry, only registered users may post in this forum.

Click here to login