Help understanding a 'reversing a string' Turing Machine

10.7k Views Asked by At

I am having a bit of a confusion understanding some transitions in a Turing Machine. Its an example from Introduction to Languages and the Theory of Computation by John C. Martin. I've attached the image below. Okay, so the confusion I have is that the transition from q3 to q8 (circled that bit) where B is being replaced by A, and the head moves to the right seems like it should be B/B instead of B/A. And same with the transition from q1 to q8 (i have circled both).

For example, if I have a string ba, it goes from q1 to q4, becomes Ba, then the head goes on until it finds a delta at the end (q2 to q3), at which point it moves to the left, and if it finds an 'a' it replaces with a 'B' (q5 to q6), so the string becomes BB. Next, the head reverses the first B to A (q6 to q1), so now its AB and at state q1, with the head pointing at B. The TM in the diagram calls for this B to be changed to A, when in fact it seems that it should remain AB, and then changed back to ab (in the state q9).

Similarly with the transition from q3 to q8, I don't see the point of B/A transition.

If I am incorrect, could anyone please help me understand this. Thank you.

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

So yes, those are needed. Note that the transitions from q5, q3 and q1 that use these go to q8. Once you're in q8, there's no going back to any other state except q9.

So those transitions mean that you've seen all your input and made them all upper case. Now it's time to convert them back to the original lower case.

In dealing with TMs and other automata, it's almost always good to ask what the state can possibly mean.