# Math Help - Turing machine

1. ## Turing machine

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"}

2. What textbook are your working with? The specifics of Turing machines may differ substantially (though they are equivalent in an important mathematical sense) from author to author.

3. I would like to understand how to determine a Turing machine for a given language

4. I don't know what "determine a Turing machine for a given langauge" means.

I asked what textbook you're using. If you don't want to tell me, then okay; but then I'm afraid I can't help you very much.

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

6. Looks fine, but do you need a reject state as well?

7. How well a state reject?

8. Originally Posted by Apprentice123
How well a state reject?
If you don't know what a reject state is, then I don't think you'll need one. It's just semantics. When the Turing machine knows it's not going to accept an input, it'll send it to a state just for rejections. i.e. a "trap state"

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

10. You understand what I did?

11. Originally Posted by Apprentice123
You understand what I did?
I haven't had the time to sit and think about it. Would you walk me through it?

12. I think it works, but not sure

13. Please if you have time, see if what I did is correct

14. Originally Posted by Apprentice123
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 $q_2$ and move back to $q_1$, you have no transitions on A and B. Also, won't it just loop between $q_1$ and $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.

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