Programming a Turing Machine

Discussion in 'C++' started by roxorsoxor2345, Dec 15, 2006.

  1. I am very sorry if this is not the appropriate group to post this
    question.

    I currently have a program that tests strings to see if they are
    palindromes. My input file looks something like this:


    0 a # R 1 (# is representation for a blank)
    0 b b R 1
    0 # # L 2
    1 a a R 2
    ..
    ..
    ..etc... (followed by a list of strings i wish to test)


    This is a transition table that works like this:
    column 1 is the current state
    column 2 is the currenty symbol on the tape (the tape contains my
    string to test)
    column 3 is what the new symbol should be
    column 4 tells the head of the tape to move left, right, or stay still.

    column 5 tells me what the new state is.


    Like I said, I have a program that works for palindromes, however I
    need to modify it to accept strings of the type (a^n)(b^2n)(c^n)


    All I need is a new transition table, and new strings to test, and I'm
    set. However I am having a tough time coming up with a working
    transition table for this problem. I know that if I could draw the
    picture I could come up with the transition table, but I can not get my

    turing machine quite right. Any help would be appreciated.
     
    roxorsoxor2345, Dec 15, 2006
    #1
    1. Advertising

  2. roxorsoxor2345

    frame Guest

    roxorsoxor2345 wrote:
    > I am very sorry if this is not the appropriate group to post this
    > question.
    >
    > I currently have a program that tests strings to see if they are
    > palindromes. My input file looks something like this:
    >
    >
    > 0 a # R 1 (# is representation for a blank)
    > 0 b b R 1
    > 0 # # L 2
    > 1 a a R 2
    > .
    > .
    > .etc... (followed by a list of strings i wish to test)
    >
    >
    > This is a transition table that works like this:
    > column 1 is the current state
    > column 2 is the currenty symbol on the tape (the tape contains my
    > string to test)
    > column 3 is what the new symbol should be
    > column 4 tells the head of the tape to move left, right, or stay still.
    >
    > column 5 tells me what the new state is.
    >
    >
    > Like I said, I have a program that works for palindromes, however I
    > need to modify it to accept strings of the type (a^n)(b^2n)(c^n)
    >
    >
    > All I need is a new transition table, and new strings to test, and I'm
    > set. However I am having a tough time coming up with a working
    > transition table for this problem. I know that if I could draw the
    > picture I could come up with the transition table, but I can not get my
    >
    > turing machine quite right. Any help would be appreciated.


    I don't know whether this might be of help to you, but I thought of the
    following "Context-sensitive grammar" for the language
    (a^n)(b^2n)(c^n):

    S -> MSN | e
    MN -> abbc
    Ma -> aM
    Mb -> abb
    cN -> Nc
    bN -> bbc

    Example: - Derivation of (a^2)(b^4)(c^2)

    S => MSN (using S -> MSN)
    => MMSNN (using S -> MSN)
    => MMNN (using S -> e)
    => MabbcN (using MN -> abbc)
    => aMbbcN (using Ma -> aM)
    => aabbbcN (using Mb -> abb)
    => aabbbNc (using cN -> Nc)
    => aabbbbcc (using bN -> bbc)

    As it's possible to construct a "linear bounded automaton" for this, a
    "Turing Machine" should also be possible.

    Clue: -
    ====

    You said that you have a program that works for palindromes, whose
    Context-free grammar should have been as follows: -

    S -> aSa | bSb | cSc | a | b | c | e

    Now figure out how the transition table is implementing the above
    grammar, then adopt the table to work for the grammar devised for
    (a^n)(b^2n)(c^n). You can do it!

    P.S.: - I am sorry if you don't find my above suggestion useful; I am a
    C++ programmer and am bit old to "Theory of Computation" :).
     
    frame, Dec 15, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Vinokur
    Replies:
    0
    Views:
    736
    Alex Vinokur
    Nov 12, 2003
  2. Alex Vinokur
    Replies:
    0
    Views:
    676
    Alex Vinokur
    Dec 19, 2003
  3. Kvele

    Turing machine

    Kvele, Jan 7, 2005, in forum: C Programming
    Replies:
    3
    Views:
    1,240
    Jack Klein
    Jan 7, 2005
  4. Matthew Moss

    [QUIZ] The Turing Machine (#162)

    Matthew Moss, May 9, 2008, in forum: Ruby
    Replies:
    26
    Views:
    529
    Matthew Moss
    May 13, 2008
  5. Matthew Moss

    [SUMMARY] The Turing Machine (#162)

    Matthew Moss, May 15, 2008, in forum: Ruby
    Replies:
    4
    Views:
    203
    Robert Dober
    May 16, 2008
Loading...

Share This Page