JAVA PROGRAM help Sample test programs for the TM class // Test Turing Machine C
ID: 3704461 • Letter: J
Question
JAVA PROGRAM help
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
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; <-- Crashes!
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
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,Explanation / Answer
Please find the below code.
public class TM {
private String[] code;
private char[] stateType;
private String tape;
private int tapePos;
private int cState;
public TM(String[] C, char[] st) {
// TODO Auto-generated constructor stub
cState = 0;
tape = "#";
tapePos = 0;
code = C;
stateType = st;
}
/**
* @return the cState
*/
public int getState() {
return cState;
}
/**
* @param cState
* the cState to set
*/
public void setState(int state) {
this.cState = state;
}
public void setTape(String tape) {
this.tape = tape;
}
public void stateTransistion(char in) {
boolean status = false;
for (String c : code) {
if (cState == Integer.parseInt(c.substring(0,1)) && c.charAt(2) == in) {
tape = tape.substring(0, tapePos) + c.charAt(5)
+ tape.substring(tapePos+1);
if (c.charAt(7) == 'L') {
if (tapePos - 1 == -1)
System.out.println("Machine Crashed");
else
tapePos--;
} else
tapePos++;
cState = Integer.parseInt(c.substring(c.length() - 1));
status = true;
return;
}
}
if (!status)
System.out.println("Machine Crashed! No transition found for the current state: "+ cState+" current symbol: " + in);
}
public boolean processData(String inString) {
tape = inString + "#";
while (stateType[cState] == 'R') {
stateTransistion(tape.charAt(tapePos));
}
if (stateType[cState] == 'H')
return true;
else
return false;
}
}
Sample input from command line
javac TMTest1.java
java TMTest1 abaa
Output: Valid String
javac TMTest2.java
java TMTest2 aabb
Output: Valid String
If we give wrong string which is not in the language then machiene crashes and it display a message saying
Machiene Crashed: No transition is found for the current state and current symbol.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.