Welcome! Log In Create A New Profile


Q5 2006

Posted by 35994908 
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
Q5 2006
May 05, 2011 08:58PM
This is the turing machine, really hope this to be correct. I am starting to get the hang of them so I really hope you don't find too much wrong with this. Let me know...

Re: Q5 2006
May 05, 2011 09:41PM
OK, like your presentation, but are the required turing machine allowed to accept baba?

Don't be different...be the one making a difference
Re: Q5 2006
May 05, 2011 09:43PM
And what happens at state 11?

Don't be different...be the one making a difference
Re: Q5 2006
May 05, 2011 09:59PM
This machine does accept baba, this should accept any even word ending in 'ba'

At state 11 it loops forever because on any word with odd length where the substring 'ba' occurs more than once. Thats apparently what a neverending loop looks like. I got that from assignment 3...

Hope this helps...
avatar Re: Q5 2006
May 05, 2011 11:37PM
Your Accept(T) implementation? Very stylish! Yes, I'm pretty sure that's about as good as you can do it.

I think you may have problems on the odd-ba bit, though.

You don't give a tinker's cuss for the non ba endings here. They can just run out of states and crash. In fact the sooner the better.

So all you really need to do is to find a way of landing back on the end of the tape forever if you find your odd-ba, right?

So now there's that loop on state 8. I think that's too kind to things you want to crash on? Do you need that loop? That would be the first question to answer. (And if the answer is yes, please tell us, because then you'll help to debug me).

Move on to state 9. You've gone left, left to get here. And you're on the odd branch. Add that up, and you've found your odd-ba. Everything else can go jump in the lake or whatever. odd-ba is all you care for.

Um. L ... L (from the delta), and you've found ba ... so you're done.

So you could replicate that nice thing you did with the the a, heading on out West again at the halt state here, surely? Make your b a (b,b, R) , anticipate finding the a again on the way back out with an (a,a,R), and then loop forever on (delta, delta, R).

How does that sound? Maybe draw the very end of the tape, and move along it with your finger in accordance with your instructions.
Re: Q5 2006
May 06, 2011 04:52PM

First of thanks for sharing, this one really had me and to get the idea to check first if the string is of even or odd length was brilliant!

Like sombody in my unisa pointed out you made a mistake at step 7(Don't worry I did it t(w)o tongue sticking out smiley)

Here is my implementation and I hope it is correct:

avatar Re: Q5 2006
May 06, 2011 07:46PM
There I go forgetting what the question said again.

Any odd one that has two or more "ba" must loop forever. All the rest of those must crash.

OK. So to find that out after testing for oddness, you'd have to rewind the entire word.

You guys are thinking outside the box and testing for "ab-backwards" instead of "ba-forwards" ... Pretty Wise, I reckon. If you find what could be the a part of ab-backwards, the next letter will be a b. If not, keep spinning on a until that b appears.

Next time you find an a, this could again be the first a of an ab-backwards. If you keep finding b's just spin there. If you find your a, go to state q9 and see if you get the b there. Yes? Then you must loop forever somehow.

For starters on that b, go Right.

And if you find an a (which you know you have) go Left again.
And if you've gone left again from a, and found a b, which you know you have, go Right again.

Where you look to see if there's an a ... R L R L R L ... ad infinitum.

Okie Dokie. The infinite loop is there and the failure to end on ba is actually not a problem for anyone who reads the bloomin question properly... Sorry for any confusion I may have caused.
Re: Q5 2006
May 06, 2011 08:13PM
Yip Eddy

This question is very tricky I drew my first (wrong) TMvery quickly with only a few states and soon realized I'm missing some key parts. The looping on more then one ba makes it tricky and also the even, odd constraint for each of the requirements.

So I will take caution in the exam and make sure I understand the question and its different but related requirements.
avatar Re: Q5 2006
May 06, 2011 10:37PM
Well I certainly hope my skill at reading questions has improved by the time exams strike.

I hope I can pull a nifty trick like just reading the required substring backwards. (And not an un-nifty trick like creating a machine not specified).
Sorry, only registered users may post in this forum.

Click here to login