Package util

Class FSM

java.lang.Object

util.FSM

All Implemented Interfaces:

Configuration

public class FSM
extends Object
implements Configuration

Deterministic Finite State Automaton (DFSA)
The FSM class defines a DFSA in terms of a 5-tuple, (Q, Σ, δ, q0, F)

• a finite set of states Q
• finite set of input symbols called the alphabet Σ
• transition function δ : Q × Σ → Q
• one initial or start state q₀ ∈ Q
• a set of accept states F ⊆ Q

The set of states, the set of actions, and the two-dimensional transition table defines the FSM. The initial state is defined by invoking State.isInitialState(), and the set of final states with invocations to State.isFinalState().

Author:

Krish Pillai

Nested Class Summary

Nested classes/interfaces inherited from interface common.Configuration

Configuration.Direction

Field Summary

Fields inherited from interface common.Configuration

AUDIO_DIR, DEFAULT_FRAME_RATE, DRAWABLE_DIR, GAMELOGGER, setViewCallChain

Constructor Summary

Constructors

Constructor	Description
FSM(State[] states, String[] actions, State[][] transitions)	Constructor for the FSM takes an array of states, actions, and the transition table.

Method Summary

Modifier and Type	Method	Description
State	getCurrentState()	Gives the current state of the FSM.
boolean	inFinalState()	Returns true if the state is designated a final state.
boolean	inInitialState()	Returns true if the state is designated a final state.
void	transition(String action)	Computes the next state for the specified action based on the transition table.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

FSM

public FSM(State[] states,
 String[] actions,
 State[][] transitions)

Constructor for the FSM takes an array of states, actions, and the transition table. The transition table is constructed as a HashMap of HashMaps. The table is built out of an associative array indexed by states. Each entry of this associative array is an associative array indexed by actions. This enables the delta function for a specific state and action to be obtained in constant time. Each row is indexed by state, in the order defined by the state array. And each column is indexed by the action, in the order defined in the actions array.

Parameters:

states - Array containing the state objects

actions - String array defining the alphabet

transitions - The 2-D transition table

See Also:

• State

Method Details

inFinalState

public boolean inFinalState()

Returns true if the state is designated a final state. There can be multiple final states

Returns:

true or false

inInitialState

public boolean inInitialState()

Returns true if the state is designated a final state. There can be only one initial state for a given FSM.

Returns:

true or false

getCurrentState

public State getCurrentState()

Gives the current state of the FSM.

Returns:

the current state

See Also:

• State

transition

public void transition(String action)

Computes the next state for the specified action based on the transition table. This method then invokes the overridden State.manage() method.

Parameters:

action - String defining the action