Welcome! Log In Create A New Profile


First Semester Students

Posted by Prof Rupie 
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
avatar Re: First Semester Students
May 04, 2011 02:11PM
Yes that sounds right to me.

Nice and abstracted from the details, too. (I suppose all these theorems we're given were meant to be useful in the end).

grinning smiley ... as long as we don't build a machine like mine or like the one in the solution it should all be fine.
Re: First Semester Students
May 06, 2011 09:49PM
Some feedback from the lecturer on this one:

There is nothing wrong with Q4 FA. Remember that the FA should accept words which have odd number of a’s OR even number of b’s. Which means aa has 0 number of b and 0 is even. As you can see NULL string is also accepted because it has 0 b’s.
avatar Re: First Semester Students
May 06, 2011 10:47PM
Well then I take back whatever it was that I took back ...

The NULL string would also have an even number of a's for that matter, come to think of it.
Re: First Semester Students
May 06, 2011 11:06PM
I hate these even = 0 = even stuff.. it can only spell disaster during an exam. This is the kind of stuff I tend to overlook in a rush...
Re: First Semester Students
May 09, 2011 05:19PM
Hi there

In tut letter 105 there is a past paper, the pumping lemma question, how do we solve tht problem because the first b in the language is to the power one. Can we let vxy consist of b only and den pump uvvxyyz and say that there's a contradiction because b occurs twice?
avatar Re: First Semester Students
May 09, 2011 06:52PM
@Tazz, there's another thread on this. I think it's under the relevant question number.

Let's see if I get somewhere. (Got lost badly on this at last attempt).

Words that are long enough pump IF the language is generated by some CF Grammar.

"Long enough" is "p letters long", I think. That's with the grammar having p live productions.

The question wants you to use the pumping lemma with length and gives it to you. There's extra info there. The middle section of the word is more than 2p letters long. That means you can take a word whose next pump (whatever that is) has to be "only of so and of so" or "all of a" etc. You can find yourself a word that doesn't have too many cases to consider.

If you find that regardless of how you split that word up (and I don't think there's a way to escape covering several cases), you never get uv2xy2z (whichever way you rearrange the word to define these), then your language cannot be a CFL. You use the pumping lemma to prove a negative.

Now as far as your b goes, I think it might help to think of it as a very convenient separator.

Imagine trying to pump a v that has aabaa for instance. If you do that twice what do you get? aabaa.aabaa, right? But now your word is of the wrong form. It can't pump that way, so v can't be that group. Work out for yourself how vxy has to be in order to stand some chance of pumping, and maybe take it from there.

OK I'm off to work on tomorrow's exam. I'll have to come and edit this waffle into something more precise tomorrow afternoon.
Re: First Semester Students
June 26, 2011 11:06AM
please forward me tutorial 101 to ishongwe@yahoo.com
Sorry, only registered users may post in this forum.

Click here to login