# Assignment 2 Question 2

Posted by BlaXpydo
Announcements Last Post
: Programming Students at UNISA School of Computing 06/19/2019 02:01PM
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
 Assignment 2 Question 2 March 17, 2011 07:14AM Registered: 9 years ago Posts: 269 Rating: 0
Hi there,

I'm having some trouble using pummping lemma to solve this problem. How do we actuall choose a word from sreverse(s)s that must come from (a + b)*?

_______________________________________
Don't be different...be the one making a difference
 Re: Assignment 2 Question 2 March 17, 2011 11:13AM Registered: 10 years ago Posts: 3,496 Rating: 1
Perhaps the first question you should ask yourself is: "Do we ever get to choose our word from sreverse?"

Another one you might try is "Which words do not come from (a + b)* ?"
 Re: Assignment 2 Question 2 March 17, 2011 12:07PM Registered: 9 years ago Posts: 269 Rating: 0
Well, you see, I actuall followed some ideas from the textbook. If there ever is a word s, then sreverse(s)s must exist. So I took a random word (say a^k a^k a^k for k>0) Found 5 cases for the pumping lemma. Then showed for those cases that the language is not context free.

Would you agree with my approach?

_______________________________________
Don't be different...be the one making a difference
 Re: Assignment 2 Question 2 March 17, 2011 12:22PM Registered: 10 years ago Posts: 3,496 Rating: 1
Sorry. I misread you there. (s, reverse(s), s)

So s determines everything else.

First thing, then is, is your word long enough? Short words do not pump.

Can you find a single exception? (All long words must pump).

Maybe this is just terminology, but I would be inclined to say you took "the arbitrary word", rather than some "random" word. I know what you mean, but if you're fussy enough about what "arbitrary" means, sometimes that can help give insight into problems.

Anyway, I can't fault your approach if your word is long enough, and it turns out not to pump. If it fails to pump just once you've contradicted a universal proposition, and it's thence not true.

As to the idea that you need to find 5 cases (I don't quite get that part of what you wrote), if that's what you think, I think you need to read the section a bit more slowly. Just to make things go faster, of course.
 Re: Assignment 2 Question 2 March 17, 2011 12:51PM Registered: 9 years ago Posts: 269 Rating: 0
Well, I took a large number (being random...or arbitrary ) and did the five cases for using the uvxyz, that would be with vxy over first s, first s and reverse(s), reverse(s), reverse(s) and final s, and then finally the final s.

I think that is what they explain in the tut102 letter....

_______________________________________
Don't be different...be the one making a difference
 Re: Assignment 2 Question 2 March 17, 2011 01:09PM Registered: 10 years ago Posts: 3,496 Rating: 1
Ah! OK, I'm being very dof today. You took cases!

Yes, that's dead right. Logically you need to do "OR-elimination" at some point in you proof.
 Re: Assignment 2 Question 2 March 17, 2011 01:52PM Registered: 9 years ago Posts: 269 Rating: 0
So in the end, after writing quite a bit, I guess I found the answer to be 'not context free'.

Would you suggest another route to take, or would this be adequate for the exam (time-wise)?

_______________________________________
Don't be different...be the one making a difference
 Re: Assignment 2 Question 2 March 17, 2011 02:10PM Registered: 10 years ago Posts: 3,496 Rating: 1
Well there are two possibilities here: Either we've both made a fairly similar mistake, or we're both right.

Case 1: Oh go on! Don't be ridiculous. If we're both on the same track it must be the right track, eh? Democratically speaking. So we're both right.

Case 2: We're both right. Obviously. So we're both right.

Then by "OR elimination" we must both be right.

Time-wise I can't see any shortcuts. I suppose if they give a time consuming exam question the compensation will be that you'll have a lot of points in the bank when you get it right.
 Re: Assignment 2 Question 2 March 17, 2011 03:39PM Registered: 9 years ago Posts: 269 Rating: 0
It seems like our result were due for a true value. Unless we consider using predicate logic, and then constructing a rather perfect model to prove that our logical way of thinking is parallel to that of formal logic proofs.

Then again, I think I'm going off topic here.

_______________________________________
Don't be different...be the one making a difference
 Re: Assignment 2 Question 2 March 17, 2011 04:08PM Registered: 10 years ago Posts: 3,496 Rating: 1

It's very dangerous to ask interesting questions. Isn't that ironic?
Sorry, only registered users may post in this forum.