The state diagram for the initial part of this turing machine given as:

enter image description here

Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back in the left direction until we find X1 again, and then we repeat the process, until both 'a' and 'c' are exhausted.

When I was trying to draw the turing machine on my own, I directly looped back from the state 'q2' to 'q0' with the transition (X1,X1,R), instead of going from 'q2' to 'q3' and then going to 'q1' as suggested in the given solution.

My question is, is my approach correct? Or will I be missing some cases or doing it wrong by skipping one state and directly looping back to 'q0'

My approach

Please shed some light on it, thanks!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.