Welcome! Log In Create A New Profile


Exam paper 2006, pumping lemma, my answer

Posted by dve83 
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
Exam paper 2006, pumping lemma, my answer
October 22, 2011 04:30PM
Herewith that second post I mentioned.

my thoughts herewith on the question 3 for pumping lemmas in 2006 exam paper.

They ask to prove that an b an+3 bn-1 is NON CONTEXT Free

So we put down the whole assumption of L is context free and thus has a CFG in CNF with p live productions and a word w with length(w) > 2p
thus we can apply the pumping lemma and thus the word w can be devided into uvxyz (5 parts) such that uvnxyz is also in L

such that

length(x) > 0
Length(v) + length(y) > 0
Length(vxy) <= 2p

i choose

i choose n to be 2p, thus each exponent n will be such (sorry dunno how to format exponent on exponent in this editor)

NOw we take this options where vxy might be.

1. It might be in a single clump of a or b
if so and if then pumped to vvxyy or more, a will be increased at one clump, but not in the others. This would result in the relationship between the first a and the second a to become null and void.
in other words before pumping we had a value of n / n+3 (or rather 2p / 2p + 3
after pumping this value will no longer be the same, because the first 2p would become (2p)n where n is the number of times pumped.
Same wouldf apply to any of the other clumps.

2. THe other option is the vxy falls over part of a's and part of b's (straddles as the book says). If so, taking the first two sets of a's and b's, when pumped it would increase either the a's or the b's or both. Again messing up the value relantioship between these a's and b's and the others.

hence all cases are contradictory to assumption.

Does this make sense.?

it seems easier with anbndncn

Danie van Eeden
Re: Exam paper 2006, pumping lemma, my answer
October 24, 2011 04:02AM
Good luck DVE...Hope we kickass with this one as well...Good luck to everyone else smiling smiley
Re: Exam paper 2006, pumping lemma, my answer
October 24, 2011 06:25AM
good luck to you too!

Danie van Eeden
Sorry, only registered users may post in this forum.

Click here to login