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

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.

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

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.

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 ?

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

How well a state reject?

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"

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

You understand what I did?

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?

I think it works, but not sure

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

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 and move back to , you have no transitions on A and B. Also, won't it just loop between and 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?