Im stuck trying to find a solution for the following turing machine:
a^nba^nba^n
I’ve got this far:
1)starting state
Read a, write x, move right, goto 2
Read x, write x, move right, goto 1
Read bottom, go to state yes
2)looking for a b
Read b, write b ,move right , goto 3
Read a,write a,move right, goto 2
3)middle segment
Read a ,write x,move right, goto 4
Read x,write x,move right, goto 3
4)looking for a b
Read b, write b ,move right, goto 5
Read a, write a, move right, goto 4
5)last segment
Read a,write x,move right, goto 6
Read x, write x,move right, goto 5
- back to beginning
Read x, write x, move left, goto 6
Read a , write a ,move left, goto 6
Read b ,write b,move left, goto 6
Read bottom, write bottom, move right, goto 1
However the issue is it accepts the empty input but the smallest acceptable input is bb where n is 0.
fyi bottom symbol=empty
>Solution :
http://turingmachinesimulator.com/shared/rhkvabaopg
I hope you will find this turing machine to your satisfaction.
It follows the same basic premise as your attempt, replacing the first a from each section with an x.
Mine differs once the end of the tape is reached after placing an x, at that point it transitions to a "chekcing mode" of three states A,B, and C. They each expect to see only a chain of x’s followed by a b, at which point it moves to the next state. If C gets to a blank entry then the tape must be of the form xxbxxbxx and the string is accepted.