org.jscience.computing.automaton.machines
Class TuringMachine

java.lang.Object
  extended by org.jscience.computing.automaton.machines.FSM
      extended by org.jscience.computing.automaton.machines.TuringMachine
All Implemented Interfaces:
Steppable, Visualizable

public class TuringMachine
extends FSM
implements Steppable

This class implements a Turing machine by deriving from a finite-state machine. The tape is simply implemented as a tape—as such, the tape is not infinite. You must allocate any space you want your Turing Machine to use in the tape itself.


Nested Class Summary
static class TuringMachine.Transition
          This class handles the Turing Machine transitions.
 
Nested classes/interfaces inherited from class org.jscience.computing.automaton.machines.FSM
FSM.State
 
Field Summary
static int ACCEPTED
          The machine acceptance state.
protected  java.lang.StringBuffer inputTape
          The input tape.
static int LEFT
          Move the tape left.
static int MACHINE_LEFT
          Move the machine left (equivalent to RIGHT).
static int MACHINE_RIGHT
          Move the machine right (equal to LEFT).
static int MACHINE_STOP
          A final, stopping state (equivalent to STOP).
protected  int machineState
          The state the machine is in (ACCEPTED, UNDECIDED, REJECTED).
static int REJECTED
          The machine rejection state.
static int RENDER_LARGE
          Set the render size of the FSM/Turing Machine as large.
static int RENDER_NORMAL
          Set the render size of the FSM/Turing Machine as normal.
static int RENDER_SMALL
          Set the render size of the Turing Machine as small.
static int RIGHT
          Move the tape right.
static int STOP
          A final, stopping state.
protected  int tapeDirection
          The direction the tape is moving in.
protected  int tapePosition
          The position the tape is in.
static int UNDECIDED
          The machine is in an undecided state.
 
Fields inherited from class org.jscience.computing.automaton.machines.FSM
currentState, fsmStates, numStates, renderSize
 
Constructor Summary
TuringMachine()
          Creates a new instance of TuringMachine
 
Method Summary
 void addTransition(FSM.State start, int transition, FSM.State end)
          Add a transition state between the specified start and end states for the given transition symbol.
 void doAnimate()
          doAnimate animates the Turing Machine transitioning from one tape position to the next.
 void doStep()
          Steps the Turing Machine using the tape position and input tape: transition(inputTape.charAt(tapePosition));
 int getMachineState()
          Return the current machine state.
 java.lang.String getTape()
          Return the input tape in non-mutable String form.
 void init()
          Initializes the Turing Machine to its default settings.
 void render(java.awt.Graphics g, int width, int height)
          Render the Turing Machine.
 void renderAsFSM(java.awt.Graphics g, int width, int height)
          Render the Turing Machine as a finite-state machine.
 void reset()
          Resets the input tape, removes all the states and calls init.
 int runMachine(java.lang.StringBuffer input, int start)
          This function simply runs the machine with a given input until the input is accepted or rejected.
 int runMachine(java.lang.String input, int start)
          This function simply runs the machine with a given input until the input is accepted or rejected.
 void setInputTape(java.lang.StringBuffer input, int start)
          Set the input tape.
 void setInputTape(java.lang.String input, int start)
          Set the input tape.
 void setRenderSize(int renderSize)
          Set the render size.
 void setTapeDirection(int td)
          Set the tape direction.
 java.lang.String toString()
          Converts the Turing Machine to a string.
 FSM.State transition(int transition)
          Transitions the Turing Machine from one state to another.
 
Methods inherited from class org.jscience.computing.automaton.machines.FSM
addState, addStates, getCurrentState, getRenderSize, getState, getStates, main, removeAllStates, setState, writeImage
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

LEFT

public static final int LEFT
Move the tape left.

See Also:
Constant Field Values

RIGHT

public static final int RIGHT
Move the tape right.

See Also:
Constant Field Values

STOP

public static final int STOP
A final, stopping state.

See Also:
Constant Field Values

MACHINE_LEFT

public static final int MACHINE_LEFT
Move the machine left (equivalent to RIGHT).

See Also:
Constant Field Values

MACHINE_RIGHT

public static final int MACHINE_RIGHT
Move the machine right (equal to LEFT).

See Also:
Constant Field Values

MACHINE_STOP

public static final int MACHINE_STOP
A final, stopping state (equivalent to STOP).

See Also:
Constant Field Values

ACCEPTED

public static final int ACCEPTED
The machine acceptance state.

See Also:
Constant Field Values

UNDECIDED

public static final int UNDECIDED
The machine is in an undecided state.

See Also:
Constant Field Values

REJECTED

public static final int REJECTED
The machine rejection state.

See Also:
Constant Field Values

RENDER_SMALL

public static final int RENDER_SMALL
Set the render size of the Turing Machine as small.

See Also:
Constant Field Values

RENDER_NORMAL

public static final int RENDER_NORMAL
Set the render size of the FSM/Turing Machine as normal.

See Also:
Constant Field Values

RENDER_LARGE

public static final int RENDER_LARGE
Set the render size of the FSM/Turing Machine as large.

See Also:
Constant Field Values

inputTape

protected java.lang.StringBuffer inputTape
The input tape.


tapePosition

protected int tapePosition
The position the tape is in.


machineState

protected int machineState
The state the machine is in (ACCEPTED, UNDECIDED, REJECTED).


tapeDirection

protected int tapeDirection
The direction the tape is moving in.

Constructor Detail

TuringMachine

public TuringMachine()
Creates a new instance of TuringMachine

Method Detail

getMachineState

public int getMachineState()
Return the current machine state.

Returns:
the machine state.
See Also:
ACCEPTED, REJECTED, UNDECIDED

setInputTape

public void setInputTape(java.lang.String input,
                         int start)
Set the input tape. The initial input tape is converted to a mutable StringBuffer. The initial position also needs to be set.

Parameters:
input - the input string.
start - the tape position.

setTapeDirection

public void setTapeDirection(int td)
Set the tape direction.

Parameters:
td - the tape direction (LEFT or RIGHT).

setInputTape

public void setInputTape(java.lang.StringBuffer input,
                         int start)
Set the input tape.

Parameters:
input - A mutable StringBuffer.
start - the initial tape position.
See Also:
setInputTape(String,int)

transition

public FSM.State transition(int transition)
Transitions the Turing Machine from one state to another. If the transition is not defined then the machine assumes that the input is valid and rejects it.

Overrides:
transition in class FSM
Parameters:
transition - the transition input.
Returns:
the new state.

addTransition

public void addTransition(FSM.State start,
                          int transition,
                          FSM.State end)
Add a transition state between the specified start and end states for the given transition symbol.

Overrides:
addTransition in class FSM
Parameters:
start - the start state.
transition - the transition symbol.
end - the end state.
Throws:
java.lang.IllegalArgumentException - DOCUMENT ME!

runMachine

public int runMachine(java.lang.String input,
                      int start)
This function simply runs the machine with a given input until the input is accepted or rejected.

Parameters:
input - the input tape.
start - the start position of the tape.
Returns:
the machine state returned.

runMachine

public int runMachine(java.lang.StringBuffer input,
                      int start)
This function simply runs the machine with a given input until the input is accepted or rejected.

Parameters:
input - the input tape.
start - the start position of the tape.
Returns:
the machine state returned.

doAnimate

public void doAnimate()
doAnimate animates the Turing Machine transitioning from one tape position to the next. The animation system animates that tape moving left or right.


doStep

public void doStep()
Steps the Turing Machine using the tape position and input tape: transition(inputTape.charAt(tapePosition));

Specified by:
doStep in interface Steppable

init

public void init()
Initializes the Turing Machine to its default settings. The tape direction as LEFT and the machine state as UNDECIDED.

Specified by:
init in interface Steppable

reset

public void reset()
Resets the input tape, removes all the states and calls init.

Specified by:
reset in interface Steppable
See Also:
init()

toString

public java.lang.String toString()
Converts the Turing Machine to a string. An example might be: Tape = 1[ ]1, State = q1, Position = 4, I/O State = Undecided Only the three most immediate tape characters are shown, as well as the current state, tape position and machine state.

Overrides:
toString in class java.lang.Object
Returns:
a string representation of the Turing Machine.

getTape

public java.lang.String getTape()
Return the input tape in non-mutable String form.

Returns:
the current input tape.

setRenderSize

public void setRenderSize(int renderSize)
Set the render size.

Overrides:
setRenderSize in class FSM
Parameters:
renderSize - the render size.
Throws:
java.lang.IllegalArgumentException - DOCUMENT ME!

render

public void render(java.awt.Graphics g,
                   int width,
                   int height)
Render the Turing Machine.

Specified by:
render in interface Visualizable
Overrides:
render in class FSM
Parameters:
g - the graphics context.
width - the width of the context.
height - the height of the context.

renderAsFSM

public void renderAsFSM(java.awt.Graphics g,
                        int width,
                        int height)
Render the Turing Machine as a finite-state machine.

Parameters:
g - the graphics context.
width - the width of the context.
height - the height of the context.