Welcome! Log In Create A New Profile

Advanced

2006 Q7

Posted by d-_-b 
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
2006 Q7
May 07, 2011 11:49AM
Hi

Here is my answer for Question 7. It feels to short for 7 marks, but I do believe it is correct.

The TM will only accept a langauge of one or multiple a(s) followed by one b, thus a+b
The TM will loop on any a langauge of one or multiple a(s) followed by one b and then one or multiple a(s), thus a+ba+b*
avatar Re: 2006 Q7
May 07, 2011 01:13PM
I suppose to get full marks you might have to point out why it behaves so.

So for instance "There's no b edge ... " ... oops ... I'm talking FA-taal there. OK in FA-sprache one would say "There is no b edge leaving the START state, so the machine will crash on any word beginning with a b"....

... and so on...

Reckon that might do it?

OK and then there's the question of whether I agree with your evaluation of the language.

I think the number of a's must be even?

And I see multiple b's ba ba ba ? But going back from b is (a, a, L). Two b's on the end goes to halt.

OK. But if an a is found after the first b, you rewind ..

Doesn't that crash?
Re: 2006 Q7
May 08, 2011 11:11PM
Why do you say it needs to be a double b? Somebody in my Unisa said the same thing. But I had a look at the TM again and the shortest word is ab:

From Start go to State 1: a
From State 1 go to State 2 : b
From State 2 go to Halt: (Delta)

As seen in the diagram below:



Also the question ask only about Accept() and Loop() so I did not concern myself with *kaboom'*s confused smiley (crashes)

So a more correct answer will be:

The TM will only accept a langauge of one or multiple a(s) followed by one b, thus a+b
The TM will loop on any a langauge of one or multiple a(s) followed by one b and then one or multiple a(s), thus a+ba+(a+b)*.
avatar Re: 2006 Q7
May 08, 2011 11:46PM
Your first loop between Start and State 1 only accepts an odd number of a's. So I was wrong about that one. If you get an even number you're back to where you started from. Try aab, for instance. Follow that with aaab.

That odd number of a's must be followed by a single b, as you rightly point out.

====

OK and then there was loop.

After the b, you can reverse if you find an a instead of the delta that takes you to halt. You'll see this one had me a bit confused back there.

so we've got a tape sort of like this aaaaaba
so T tells us to go L. aaaaaba
so we land on that b again, which will be followed by the a on this tape (because we're overwriting b with b and a with a at this point). We're in a loop.

And after that a, what would there be on the Tape?

aaaaabajinglebellsjinglebellsjinglealltheway ... absolutely anything...

Well not absolutely because sigma = {a,b}

If you reach the a after the b, you're stuck forever. So loop a would be for any word starting with ....

Maybe that's the way to do it? Rough work is a piece of the tape, which you execute the moves on, so as to see what's going on? Certainly I've only really gotten this by actually "drawing that tape" for myself. I was stuck before that, as you can easily see.

So I suppose I owe you some thanks for forcing me to find enlightenment. grinning smiley
Sorry, only registered users may post in this forum.

Click here to login