Welcome! Log In Create A New Profile

Advanced

First Semester Students

Posted by Prof Rupie 
Announcements Last Post
Announcement myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
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
avatar First Semester Students
February 22, 2011 02:46PM
If your registered for this module then lets get down to bussiness.hot smiley
Anonymous User
Re: First Semester Students
March 01, 2011 02:38PM
I can't believe we have to do this in four months. the contents is quite a lot. i study this module every day but it seems is not enough
avatar Re: First Semester Students
March 05, 2011 06:51PM
You'll be right if you're studying every day. It all interrelates, and the first section very much relates to/ draws on all the work you did on the first section. You're already inducted into the way of thinking, so it's just a matter of carrying forward with that.

That theorem in Ch15 is a bit heavy going, but actually if you compare it to Kleene, it's almost a walk in the park. (OK so I exaggerate -- but it is easier than Kleene by some amount).

The pumping lemma stuff is basically practical, more than theoretical. Do a few and it all makes sense (at least for about 2 weeks or so)... Ja, and then I recall the Turing Machines at the end were just a wonderful finish to the first skim through. Had to stop to take in the scenery every now and then, so to speak.

It's probably a very idea to do all the assignments, for starters.

OK, so now I can finish by agreeing with you that it's a lot of work. It's double the previous one. But it's manageable. Just plod on through the next 2 months and you'll get as far as any of the rest of us ordinary human beings the exam will eventually be pitched at. That's all you really need to manage to survive.
avatar Re: First Semester Students
March 06, 2011 12:55AM
Just an experiment in using the phorum quoted text facility (I mean what harm can playing in a dead thread do, eh?)

Quote
crunx
I can't believe we have to do this in four months. the contents is not a lot. however, i study this module every day and so I'm always hitting it for a six.

This is by clicking that quotation mark up there. It asks whom to blame for the quotation, and then you just cut and paste (and maybe misquote if you like) into the tag pair that is produced.
avatar Re: First Semester Students
March 06, 2011 01:04AM
OK. And now for the quoted code option.

Again I do a difficult click, which gives a set of unusual tags, once again.

Language: C++
#include<some_include> void someFunction(string blah){ int test_indent; double trois_lines; char this_fragment_just_declares_variables_with_bad_names; \* I suppose one should do something with that * * blooming blah I pass to this fake function. * * This is just an excuse to make the comment * * all pretty pretty. \* userError oops_that_comment; cout << blah << endl; }

The moral of the story might be "Don't just copy and paste your code. Copy and paste it inside formatted code tags."
Re: First Semester Students
March 07, 2011 11:04AM
can anyone having last year material cos3701 to forward it to me at zeb@webmail.co.za. thanks in advance
Re: First Semester Students
March 14, 2011 07:09PM
Hi there,

Does anybody have old tut letters or any other info or guideline abt this course ple send to
me.
My email address is 44526369@mylife.unisa.ac.za
Re: First Semester Students
March 14, 2011 07:11PM
Hi,
Anybody managed to answer question 3 assignment 2, I'm really struggling with it.
Will appreciate any guidelines or tips
avatar Re: First Semester Students
March 14, 2011 07:54PM
Quote
Tazz
Hi,
Anybody managed to answer question 3 assignment 2??? I'm really struggling with it finding it mildly challenging, but
will appreciate any guidelines or tips
(Great fun this, ay, shipmates! Anyone else as delighted with this course as I am.)

I think the way I got through it was to follow Cohen's tip. First convince yourself that his tip to the question is correct, then make a few actual words, being very careful to keep the restrictions on numbers given in the superscripts. Pump them. See what happens. Start with small words, then get bigger (just keeping an eye on those restrictions).

I can't properly remember in detail how I went about it, but I know I did the "small experiments", and those helped somewhat.

If that's completely useless to you, please let me know, and I'll try to dig a bit and find something more useful to say. (Also helps me check that I'm on the right track).

Um.. you might want to try and see what happens if you drop the restriction (as mentioned in the next question in the text book).

My insincere apologies for editing what you said. grinning smiley
Re: First Semester Students
March 15, 2011 11:18AM
Hey there slow eddy,
I must admit I guess I am bit of a drama queen. Lol.
After applying the restrictions, I figured that the words in this language will be of the form : a^n b^2n a^4n b^3n where n = 1, 2 , 3 ....

But now I get stuck as to how to build a CFG for the above. It has to be infinite.
Am I on the right track in my thought process?
avatar Re: First Semester Students
March 15, 2011 01:13PM
Look a bit more carefully at the condition, and write out the smallest word in the language.

(Literally. If it's aaaaabaaaaabaaaa, that's what to write)

The CFG would have to infinite/ non-terminating, yes, but that's just one part of it. I mean, what about the individual words of the language? They all have to terminate, don't they?

Oh.. and once you've written the smallest word, break it up according to the pattern in Cohen's tip, so you can see what to pump.

Hmm, I look at my own answer now and a bit of doubt creeps in. Will have to convince myself it's OK again.
Re: First Semester Students
March 17, 2011 10:42AM
Hi there,
Think I might have finally figured out da answer, not too ecstatic abt it though. The CFG does produce all the words in the language problem is, it also produces words tht aren't in the lanfuage.
avatar Re: First Semester Students
March 17, 2011 11:09AM
If it's producing words that aren't in, you're right to be less than ecstatic. Back to the drawing board again, I fear.

How about trying a recursive definition of some portion of the language? I have no clue if that would help, but who knows?

As to words of the language (in terms of the base definition, and not in terms of that pattern - ie. ITO the constraints) maybe look carefully at the equations again? Could be that you're missing a few words by making the equations "more exclusive" than they really are? I seem to remember that at the extremes the pattern was not quite exactly the same (to outward appearances) as "in the middle".
Re: First Semester Students
March 23, 2011 11:32AM
Hey there eddy
I finally cracked Q2. It seems I was on the right track, my answer just needed lil tweeking. I'm gonna go submit it on Friday. I hav to go to Unisa regional office and hand it in, cos I mistakely already submitted in the wrong doc for ass2 and the status closed on myunisa, resubmit didn't appear.
avatar Re: First Semester Students
March 23, 2011 11:42AM
Yes it looked on the right track. As you say, just a little tweaking.

I see on myUnisa the lecturer also said to follow Cohen's tip, so that starting point is also correct.

Anyway, well done! Good on you for sticking at it till it cracked.
Re: First Semester Students
March 23, 2011 11:46AM
Yeah, at least now I can start full blow with studies for exams. I'm just finding it so hard to conc , I had a pretty tragic weekend. Some1 I know commited suicide and I really haven't been sleeping well. I think its worst that the person lived in the first floor of our building and it happened there.
avatar Re: First Semester Students
March 23, 2011 12:49PM
Yes it's always a shock when someone you know commits suicide. Often they don't even appear suicidal on the outside, which makes it even more perplexing. Don't even try to understand it. That was someone else's life, not yours, and for some reason you'd best hope never to understand, they lost perspective and ended it.

You'll be right. Even when your emotions are telling you you're not thinking well, often the fact of the matter is that actually you are. It just doesn't feel as nice thinking things out as it usually does, that's all. Trick is to somehow ignore the feelings. For instance when you have to work through something you find difficult with a head cold it never feels like you managed properly, but often enough if you later reread what you did you can't distinguish it from something from a great day. (Just downscaling from suicide of acquaintance here).
Re: First Semester Students
March 23, 2011 12:56PM
Well I guess you right , its a bit too late to ponder upon now. All I can do is best get on with my life. I guess I better be strong for my lil bro, he's doing matric this year.
Thanks for the advice. I guess sometimes it takes a stranger to knock some sense back into you.

Thanks again. Hey what's your e-mail address, Reanie sent me some past year stuff for COS301 I can pass it to you as well.
avatar Re: First Semester Students
March 23, 2011 01:29PM
Glad to be of assistance, and thanks. (See PM).
Re: First Semester Students
April 29, 2011 10:55AM
Hi everyone.

I think the FA for Question 4 on tut 201 is wrongthumbs down, since it generates even a's instead of odd a's check the first loop from the first state -S to the final state +A and back to final state +S which generates aa we need not go father. Remember aa is not allowed by our regular expression [r=a(aa)*+(bb)*], thus the given FA is wrong without a doubt. What do you think?smoking smiley
avatar Re: First Semester Students
April 29, 2011 11:33AM
Yep, I reckon you're right. How to fix the machine? I would go for an aa on the "return leg" from A-->S.

Would that do it?

And then I suppose the next thing to do is to check that grammar to see if there wasn't just a typo...

Nope. Grammar is also wrong. S->aA , aA->aaS, aaS -> aa[lambda] and there we have an even string.

smile You must be a professor or something.
avatar Re: First Semester Students
April 29, 2011 11:57AM
No I'm not a professor, it is just my nickname.smile

The correct FA should have atleast five states with S(start) as both start and final and maybe +A as another final state which will accept a adges from S and say B state which will accept b edges from S and back to S whenever b is read. if we read an a we go to +A thus we have a which is accepted and if we read an a at +A we go to say X and go back to +A whenever a is read. If we read a b at any of three states +A, B or X we go to Z which is a dead end (i.e. if we read a or b at Z we go back to Z). Thus our CFG will look nlike this:
S->aA|bB|/\
A->aX|bZ|/\
B->aZ|bS
X->aA|bZ
Z->aZ|bZ
smoking smiley
avatar Re: First Semester Students
April 29, 2011 12:01PM
So am I right?
avatar Re: First Semester Students
April 29, 2011 01:02PM
Hmm ... The way I've drawn it I pick up some problems.

First B as an accept state gives odd b accepts. I would think you have to have a loop from S through b and back to S? (On b edges. I'm still thinking about what to do with a edges from B in that case - other than following the diagram in the TL, roughly)...

How about replacing the aa edges with an additional middle state on the return edges? So we have 6 states with a small adaptation of the TL machine. So your loop from A to X to A on reading an a goes straight back to S instead.

Then there's the issue of b's coming out of A, and a's coming out of B. If a b out of A went straight to B (and B was in a loop from S), then its return journey would make for an even number of b's if it were followed by a b.

OK now I'm getting tangled. Let me draw a diagram and describe that, rather.
avatar Re: First Semester Students
April 29, 2011 01:18PM
How would four states please you?

S ---------> A
<--X<--- for a edges on that side of town

S-----------> B
<--------- to ensure even b edges

So then A and X b's ? Easy A -------> B <--------- X (so add one to return to the accept state, and you have 2 in total for this section of the journey.)

And finally a's from B? B ----------> A (start of an odd number?). «edit» I imagined I was mistaken, but I was wrong. smile

Mind you that OR means that you simply have to guarantee one of: Odd a's ; Even b's, and you're home and dry.
avatar Re: First Semester Students
May 03, 2011 11:44AM
"Mind you that OR means that you simply have to guarantee one of: Odd a's ; Even b's, and you're home and dry."
We all know what OR means and the idea is to design a flexible machine for the user, remember that we are working on the desingner's perspective and a one sided solution will result in a bad design. If we choose to either consider odd a's or even b's we should be able to do so without problems. Try to run atleast five strings of odd a's and of even b's on my CFG and see if you get problems(ie. first draw a correct FA for the given CFGsmoking smiley).
avatar Re: First Semester Students
May 03, 2011 12:02PM
Yes, I must've drawn it wrong somehow. Grammar certainly looks OK.
avatar Re: First Semester Students
May 03, 2011 12:49PM
Try this CFG:

S->aA|bB|/\
A->aX|bA|/\
B->aB|bS
avatar Re: First Semester Students
May 03, 2011 01:29PM
Ja, ja, OK..

Looks like anything with a lambda will thereby be an accept state?
Re: First Semester Students
May 04, 2011 01:25PM
I thought this could somehow be solved by using Kleene's theorem (chapter 7 I think)..
You take FA1 which is all strings with an odd number of a's
and FA2 which is all strings with an even number of b's
Then you create a new FA consisting of FA1 + FA2..
Unless I've got it all wrong, + is equivalent to OR and such a machine should generate the correct language regardless of our interpretation of the rules..
Sorry, only registered users may post in this forum.

Click here to login