Welcome! Log In Create A New Profile

Advanced

Oct 2006 Exam Question 3.

Posted by ian.coetzer 
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
Oct 2006 Exam Question 3.
November 02, 2009 02:45AM
Not 100% sure about this, but take a look this is my first stab at this beast.

2006 3)

Bye
Re: Oct 2006 Exam Question 3.
November 02, 2009 02:00PM
This is my attempt, I'm not so sure I've covered all the bases properly when it comes to vxy being split across two groups of letters. My thinking was that because of the single b after the first group of a's the only sensible way of splitting the word up would be across the third and fourth groups HOWEVER suppose you could still say that splitting it across groups 1 and 2 or 2 and 3 would always result in more a's than there should be, only one letter of vxy would be b and the rest a's.

Assume L is context-free. Therefore there is a CFG with p live productions that generates L. Every word w in L with length(w) > 2^p can be broken into five parts uvxyz such that
length(vxy) <= 2^p
length(x) > 0
length(v) + length(y) > 0
and such that all words u(v^n)x(y^n)z with n >= 2 are also in L.

Choose a word from L that has length > 2^p e.g. [a^(2^p)]b[a^((2^p)+3)][b^((2^p)+1)]. Now consider ways of breaking up the word. We know that length (vxy) > 0 which means it is contained in either a single group of the same letter or spread across two groups of letters.

Suppose vxy was contained in the first group of a's and n = 2, the word uvvxyyz will contain more than 2^p a's and therefore will not be in L. Similarly if vxy were in the secong group of b's and n = 2, the word uvvxyyz would contain more than (2^p)-1 b's and so not be in L. The second group of a's could not contain vxy because there are (2^p)+3 letters and so length(vxy) > 2^p.

The only siuation where vxy could be split across two groups of letters is across the second group of a and b. In this situation the word uvvxyyz would not be in L because there would either be more than (2^p)+3 a's or more than (2^p)-1 b's in the word.

In summary, have shown that every way in which a^(2^p) b a^(2^p)+3 b^(2^p)+1 can be split into uvvxyyz results in the word not being in L which then contradicts the pumping lemma and so contradicts the initial assumption and therefore L is not context-free.
avatar Re: Oct 2006 Exam Question 3.
November 03, 2009 10:30AM
For a2pba2p+3b2p-1, vxy =
1. only a's from first clump
2. 2p-1 a's of first clump and first b
3. a's from first clump, first b, a's from second clump
4. first b, 2p-1 a's from second clump
5. only a's from second clump
6. a's from second clump and b's from second clump
7. 1 a from second clump, 2p-1 b's from second clump

--
"A man is the less likely to become great the more he is dominated by reason: few can achieve greatness - and none in art - if they are not dominated by illusion." Mr. Doctor
Re: Oct 2006 Exam Question 3.
November 03, 2009 10:38AM
Huh?
Re: Oct 2006 Exam Question 3.
November 03, 2009 10:39AM
Lol, I think malberts is trying to tell us that there are 7 possible cases in which the suitable word can be broken up,
since vxy <= 2^p
Re: Oct 2006 Exam Question 3.
November 03, 2009 10:43AM
Must be a case of reading between the lines
Re: Oct 2006 Exam Question 3.
November 03, 2009 01:15PM
LOL, was wondering how you posted with superscripts but now I see the toolbar has a button for it, idiot!
Re: Oct 2006 Exam Question 3.
November 03, 2009 01:17PM
lol, I see it too now! I would like it if the forums allowed one to embed images.
It used t support this about 3 years ago when i posted image tags it would embed them so that one could see the image and did not have to click on the link.
Sorry, only registered users may post in this forum.

Click here to login