# Pumping Lemma with length

Posted by jeanbodemer
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
 Pumping Lemma with length November 17, 2007 10:33PM Registered: 14 years ago Posts: 470 Rating: 0
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 Registered: 12 years ago Posts: 457 Rating: 0
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 Registered: 14 years ago Posts: 470 Rating: 0
Thank Iva!
 Re: Pumping Lemma with length November 18, 2007 06:58PM Registered: 12 years ago Posts: 2,813 Rating: 0
thanks!!!
 Re: Pumping Lemma with length November 18, 2007 08:54PM Registered: 13 years ago Posts: 69 Rating: 0
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 Registered: 12 years ago Posts: 457 Rating: 0
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
GOOD LUCK EVERYONE FOR TOMRROW i'm outa here
 Re: Pumping Lemma with length November 19, 2007 01:39AM Registered: 12 years ago Posts: 2,813 Rating: 0
just wrote, good luck guys (and gals, but we all know iva's gonna smash it )
Sorry, only registered users may post in this forum.