# Exam paper 2006, pumping lemma, my answer

Posted by dve83
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
 Exam paper 2006, pumping lemma, my answer October 22, 2011 04:30PM Registered: 13 years ago Posts: 129 Rating: 1
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 Registered: 8 years ago Posts: 25 Rating: 0
Good luck DVE...Hope we kickass with this one as well...Good luck to everyone else
 Re: Exam paper 2006, pumping lemma, my answer October 24, 2011 06:25AM Registered: 13 years ago Posts: 129 Rating: 1
good luck to you too!

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