How does the Turing machine?
Please could someone explain with an example. Like this:
Develop a turing machine that accepts the language
1) L1 = {W E {a,b}^* / the third symbol of W is "a"}
My attempt:
I -> symbol of the beginning of tape
R -> Move to right
L -> Move to left
P -> Special blank symbol
A --- (a1,a2,m) ---> B
A = previous state
a1 = symbol read
a2 = symbol written
m = direction of movement
B = new state
My attempt for the language that I asked
q0 => (I,I,R) to q0
q0 => (a,A,R) to q1
q0 => (b,B,R) to q1
q1 => (a,A,R) to q2
q1 => (b,B,R) to q2
q2 => (a,A,R) to q3
q3 => (P,P,R) to q4
q4 is end state
Are correct ?
OK. Thanks
For this language:
L2 = {w E {a,b}^* / the third symbol W from right to left is "a"}
q0 => (I,I,R) to q0
q0 => (a,A,R) to q1
q0 => (b,B,R) to q1
q1 => (a,A,R) to q2
q1 => (b,B,R) to q2
q2 => (a,A,L) to q1
q2 => (b,B,L) to q1
q2 => (a,A,R) to q3
q3 => (a,A,R) to q4
q3 => (b,B,R) to q4
q4 => (a,A,R) to q5
q4 => (b,B,R) to q5
q5 => (P,P,R) to q6
q6 is end state
Are correct ? I'm finding very large
I don't think this works. For starters, when you're at $\displaystyle q_2 $ and move back to $\displaystyle q_1 $, you have no transitions on A and B. Also, won't it just loop between $\displaystyle q_1 $ and $\displaystyle q_2 $ forever if you fix that?
What I would do, and maybe there's and easier way, is to write a turing machine to reverse the order of your input string, then use this new string as an input for the first turing machine you wrote in this thread.
Friend, I studied more and I think I understand the workings of the Turing machine. I did a problem a bit more complicated
L={W E {a,b}^* / W = ba^{2n+1} n>=0}
Look my solution
q0 => (I,I,R) to q0
q0 => (b,B,R) to q1
q1 => (a,A,R) to q2
q1 => (A,A,R) to q2
q2 => (a,A,L) to q1
q2 => (A,A,R) to q3
q3 => (a,A,L) to q2
q3 => (A,A,R) to q2
q3 => (P,P,R) to q4
q4 is end state
I tested for the word: baaaaa and ran. I think the algorithm works for ba^{2n+1}
I can read and write the same letter? As in (A, A, R) right?
I need some error message when you test a word that does not belong to language?