Q5 2006

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...

OK, like your presentation, but are the required turing machine allowed to accept baba?

_______________________________________
Don't be different...be the one making a difference

And what happens at state 11?

_______________________________________
Don't be different...be the one making a difference

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...

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.

Hi

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 )

Here is my implementation and I hope it is correct:

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.

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.

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).