Results 1 to 15 of 15

Math Help - Turing machine

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    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"}
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2008
    Posts
    829
    I would like to understand how to determine a Turing machine for a given language
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Looks fine, but do you need a reject state as well?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2008
    Posts
    829
    How well a state reject?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Apprentice123 View Post
    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"
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Jun 2008
    Posts
    829
    You understand what I did?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Apprentice123 View Post
    You understand what I did?
    I haven't had the time to sit and think about it. Would you walk me through it?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Jun 2008
    Posts
    829
    I think it works, but not sure
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Please if you have time, see if what I did is correct
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Apprentice123 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing Machine Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2011, 11:14 AM
  2. Non-polynomial Turing Machine
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: December 12th 2010, 12:04 AM
  3. Turing Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2010, 06:39 AM
  4. Turing machine: help neeed
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: June 3rd 2008, 12:45 AM
  5. Turing Machine Problems
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 5th 2008, 11:27 PM

Search Tags


/mathhelpforum @mathhelpforum