org.generation5.ai
Class TuringMachine

java.lang.Object
  org.generation5.ai.FSM
      org.generation5.ai.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 inherited from class org.generation5.ai.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.generation5.ai.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.generation5.ai.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.

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.

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.

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.