Results 1 to 2 of 2
  1. #1
    bladeb2k is offline Member
    Join Date
    Aug 2007
    Posts
    1
    Rep Power
    0

    Default Turing machine Help please!!

    Can anyone help me with this problem or point me in the direction of somewhere that can, i wuld be extreamly grateful.

    Q) The range of data to be accepted by the program has been extended to allow numbers to be grouped within parenthesis eg. 01,{01,0,{10,1,{0,1},{1}}},1

    Design a Turing machine which will check for correctly formatted data. In this version the restriction of 0 being only represented by a single symbol need not be adhered to. The TM should check for correctly matched {and} but need not detect misplaced commas (as in, eg. {0,}).

    You should assume:

    i) the data is initially positioned on an otherwise blank tape (i.e. all spaces) with the TM's reading head above the first character.

    ii) All commas are legally placed but {and} may not be

    iii) the TM will end in one of the following states:

    VALID DATA

    TOO MANY '}'

    TOO MANY '{'

    with the obvious interpretation.

  2. #2
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    9

    Default

    Java Code:
    public class BraceCheck {
        public static void main(String[] args) {
            String[] tapes = {
                "01,{01,0,{10,1,{0,1},{1}}},1",
                "1,0,0{0}},{{{1,0}},1,0}",
                "0,1,{{0,0},{1},{{{0}},1"
            };
            for(int j = 0; j < tapes.length; j++) {
                System.out.printf("checkBraces(tapes[%d]): = %s%n",
                                   j, checkBraces(tapes[j]));
            }
        }
    
        private static String checkBraces(String tape) {
            int len = tape.length();
            //System.out.println("len = " + len);
            int headPos = 0;
            // Find first left brace.
            while(tape.charAt(headPos) != '{' && headPos < len)
                headPos++;
            int leftBraceIndex = headPos;
            //System.out.printf("leftBraceIndex = %d%n", leftBraceIndex);
            // Find index of a matching right brace.
            int match = 0;
            do {
                headPos++;
                if(tape.charAt(headPos) == '{')
                    match--;
                if(tape.charAt(headPos) == '}')
                    match++;
            } while(headPos < len-1);
    
            String result = "ILLEGAL STATE";
            if(match < 1)
                result = "TOO MANY '{'";
            if(match == 1)
                result = "VALID DATA";
            if(match > 1)
                result = "TOO MANY '}'";
            return result;
        }
    }

Similar Threads

  1. How to get URL from network machine
    By Mir in forum Networking
    Replies: 1
    Last Post: 04-02-2008, 01:08 AM
  2. Getting name/ip of a machine
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 03-02-2008, 08:11 PM
  3. Too many virtual Machine
    By davantmay in forum Java Applets
    Replies: 1
    Last Post: 07-06-2007, 11:53 PM
  4. Virtual Machine To Pda
    By Heather in forum Advanced Java
    Replies: 2
    Last Post: 06-30-2007, 04:11 PM
  5. Visual Turing Machine 2.0
    By levent in forum Java Software
    Replies: 0
    Last Post: 05-31-2007, 10:24 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •