JAVA PROGRAM help

Suggested Pseudocode for processData() and stateTransition() methods of TM

class:

Consider: stateType array indicates if a state is a Halt state ('H') or

effectively a Reject (potential Crash) state ('R')

Consider: crash occurs if (a) no outgoing transition exists for a given state or

(b) the tape head is moved Left from the leftmost cell position on the tape

processData(inString : String) : boolean

Place input string on tape (remember to place at least one "delta"

character (#) at the end of the string)

while current state is 'R'

Call stateTransition(character at current tape head position)

end while

if(stateType of current state is 'H')

return true;

else

return false;

end processData

stateTransition(inChar: char) : void

for each instruction in Code array

search for an existing branch from current state

end for

if branching instruction exists

write new character at current tape head position

move tape head to new location (check for crash!)

set the machine to the new state

else

machine crashes

end stateTransition

Sample test programs for the TM class

// Test Turing Machine Class public class TMTest1 {

public static void main(String[] args) {

// Language: strings in which the second letter is b String[] C =

{"0,a=>a,R,1", "0,b=>b,R,1", "1,b=>b,R,2", "2,a=>a,R,2", "2,b=>b,R,2", "2,#=>#,R,3"};

char[] ST = {'R','R','R','H'};

String inString; boolean accept1; TM TM1 = new TM(C, ST); if(args.length >= 1){

// Input string is command line parameter inString = args[0]; // Process input string accept1 = TM1.processData(inString); System.out.println(" Valid string?

} }// end main

} // end class

// Test Turing Machine Class public class TestTM2 {

public static void main(String[] args) {

// Language: strings with N a's followed by N b's String[] C =

{"0,a=>A,R,1", "1,a=>a,R,1", "1,B=>B,R,1", "1,b=>B,L,2", "2,a=>a,L,3", "2,B=>B,L,2", "2,A=>A,R,4", "3,a=>a,L,3", "3,A=>A,R,0", "4,B=>B,R,4", "4,#=>#,R,5"};

char[] ST = {'R','R','R','R','R','H'};

String inString; boolean accept1; TM TM1 = new TM(C, ST); if(args.length >= 1){

// Input string is command line parameter inString = args[0]; // Process input string accept1 = TM1.processData(inString); System.out.println(" Valid string?

} }// end main

} // end class

Write a TM class that meets the following design specifications: Instance variables: String Code char[] StateType String Tape int int - state transition function as code -- ='H' if Halt state -read/write tape (input string is data) -- tape head position -- current state tape Pos cstate Constructor TM (String[] C, char[] ST) Assume that the current state is initialized to 0, the tape is initially empty ('#' symbol) and the starting position of the tape head is at the left end of the tape (position 0). Note that the '#' symbol in our simulation is equivalent to the A symbol used in the text. Methods: int getState () and void setState (int) void setTape (String) void stateTransition (char) boolean processData (String) The TM class includes an instance variable Code that is an array of type String. Each Code string defines a program "statement." A statement represents the machine actions for one set of inputs (current state and input symbol). The TM statements contain five fields: int state1 char inSymbol char outSymbol char moveLR int state -- current state -read symbol from tape -- print symbol to tape ?move tape head position (L or R) -- next state The instruction format for a Turing machine is: statel, inSymbol->outSymbol, moveLR, state2 For example, the statement "O ,a=>A, R, 1" specifies that when the current state is 0 and the symbol a is read from the tape, then A is printed on the tape, the tape head is moved right (R), and the next state is 1, Write a TM class that meets the following design specifications: Instance variables: String Code char[] StateType String Tape int int - state transition function as code -- ='H' if Halt state -read/write tape (input string is data) -- tape head position -- current state tape Pos cstate Constructor TM (String[] C, char[] ST) Assume that the current state is initialized to 0, the tape is initially empty ('#' symbol) and the starting position of the tape head is at the left end of the tape (position 0). Note that the '#' symbol in our simulation is equivalent to the A symbol used in the text. Methods: int getState () and void setState (int) void setTape (String) void stateTransition (char) boolean processData (String) The TM class includes an instance variable Code that is an array of type String. Each Code string defines a program "statement." A statement represents the machine actions for one set of inputs (current state and input symbol). The TM statements contain five fields: int state1 char inSymbol char outSymbol char moveLR int state -- current state -read symbol from tape -- print symbol to tape ?move tape head position (L or R) -- next state The instruction format for a Turing machine is: statel, inSymbol->outSymbol, moveLR, state2 For example, the statement "O ,a=>A, R, 1" specifies that when the current state is 0 and the symbol a is read from the tape, then A is printed on the tape, the tape head is moved right (R), and the next state is 1