Build a deterministic Turing machine that decided L = {ww}

This is a discussion on Build a deterministic Turing machine that decided L = {ww} within the Tech Board forums, part of the Community Boards category; Code: w is in {a, b}^* I thought that I would go until the end of the input and then ...

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675

    Build a deterministic Turing machine that decided L = {ww}

    Code:
    w is in {a, b}^*
    I thought that I would go until the end of the input and then go back in the middle and insert a '#'. Then I know how to solve this problem. The input will have as first char a special symbol |_| and will end with this symbol too. So an example of accepted input would be this one:
    Code:
    |_|abaaba|_|
    I do not know how to go back in the middle or how to measure the length of the input. I do not know however the tools to do that! Any idea?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    The algorithm will go like this:
    Make the first char an upper one. Go to the last char and convert it to an upper one. Do this until no lower chars exist.
    Now the "pointer" is set on the first letter of the 2nd string of the middle.
    Make all the chars of the 2nd string (i.e. after the middle of the input, which we found as described above).
    Then parse the input and when you have a match, place a blank. You are done when tape has only blanks.
    Now, I do not know how to express this in Turing machine language, with δ() and all this, but I will have to search..
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Yep, it worked. I did some modifications to my approach, but this should be enough for someone to get started. If someone wants more info, let me know.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    I think you are making this needlessly complicated.
    Replace 1st symbol with _
    Traverse to the end of the input with a state that remembers what the 1st symbol was.
    If matches, replace with _, go back and continue doeing the same for the smaller string.
    Otherwise go to an invalid state and end.
    Stop when all input is consumed.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  5. #5
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    This would work too! Thnx!
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. program to read in a deterministic finite automata from a file
    By mrsirpoopsalot in forum C Programming
    Replies: 2
    Last Post: 10-15-2011, 05:53 PM
  2. Deterministic finite automata programming
    By sholex in forum C++ Programming
    Replies: 3
    Last Post: 12-18-2010, 12:45 PM
  3. C++ Turing machine
    By Dante Wingates in forum General Discussions
    Replies: 5
    Last Post: 07-26-2010, 01:47 AM
  4. Turing Machine
    By Brad C in forum Tech Board
    Replies: 2
    Last Post: 08-05-2005, 08:22 PM
  5. IDEA: Turing Machine
    By ygfperson in forum Contests Board
    Replies: 0
    Last Post: 08-12-2002, 11:08 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21