org.metasyntactic.math.automata
Class AbstractFiniteAutomata

java.lang.Object
  |
  +--org.metasyntactic.math.automata.AbstractFiniteAutomata
All Implemented Interfaces:
FiniteAutomata, java.io.Serializable
Direct Known Subclasses:
GeneralizedNondeterministicFiniteAutomata, NondeterministicFiniteAutomata, PushdownAutomata

public abstract class AbstractFiniteAutomata
extends java.lang.Object
implements FiniteAutomata

Abstract class implementing base functionality for a finite state machine, such as a NondeterministicFiniteAutomata or a DeterministicFiniteAutomata.

See Also:
Serialized Form

Field Summary
protected  java.util.Set acceptStates
          F⊆Q is the set of accept states
protected  java.util.Set alphabet
          Σ is a finite alphabet
protected  java.lang.ref.SoftReference cachedTable
           
protected  boolean decision
          The return value of accept if immedateDecisionPossible is true.
protected  boolean immedateDecisionPossible
          In certain cases it is possible to know immediately if this machine will accept the string passed to it.
protected  java.lang.Object startState
          q0∈Q is the start state
protected  java.util.Set states
          Q is a finite set of states
protected  TransitionFunction transitionFunction
          δ:Q x Σε→Q is the transition function
 
Constructor Summary
AbstractFiniteAutomata()
           
 
Method Summary
 java.util.Set getAcceptStates()
          Returns a mutable view of the accept states of this machine.
 java.util.Set getAlphabet()
          Returns a mutable view of the alphabet of this machine.
 java.lang.Object getStartState()
          Returns a mutable view of the start state of this machine
 java.util.Set getStates()
          Returns a mutable view of the states of this machine.
 TransitionFunction getTransitionFunction()
          Returns a mutable view of the transition function of this machine.
 java.lang.String[][] toStateTable()
          Returns a convenient view of this FiniteAutomata as a 2 dimensional array.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface org.metasyntactic.math.automata.FiniteAutomata
accept
 

Field Detail

states

protected java.util.Set states
Q is a finite set of states


alphabet

protected java.util.Set alphabet
Σ is a finite alphabet


transitionFunction

protected TransitionFunction transitionFunction
δ:Q x Σε→Q is the transition function


startState

protected java.lang.Object startState
q0∈Q is the start state


acceptStates

protected java.util.Set acceptStates
F⊆Q is the set of accept states


immedateDecisionPossible

protected boolean immedateDecisionPossible
In certain cases it is possible to know immediately if this machine will accept the string passed to it. For example a finite machine with no accept states will never accept, and so we can reject all inputs without wasting CPU time. This field is set to true if we can make a decision without reading any input. If this field is true then accept should return decision.

See Also:
decision

decision

protected boolean decision
The return value of accept if immedateDecisionPossible is true.

See Also:
immedateDecisionPossible

cachedTable

protected java.lang.ref.SoftReference cachedTable
Constructor Detail

AbstractFiniteAutomata

public AbstractFiniteAutomata()
Method Detail

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

getStates

public java.util.Set getStates()
Returns a mutable view of the states of this machine. Note: Modifying this value can have an adverse affect on the instance of the class it was called on. Do so at your own risk!

Returns:
a mutable view of the states of this machine

getAlphabet

public java.util.Set getAlphabet()
Returns a mutable view of the alphabet of this machine. Note: Modifying this value can have an adverse affect on the instance of the class it was called on. Do so at your own risk!

Returns:
a mutable view of the alphabet of this machine

getTransitionFunction

public TransitionFunction getTransitionFunction()
Returns a mutable view of the transition function of this machine. Note: Modifying this value can have an adverse affect on the instance of the class it was called on. Do so at your own risk!

Returns:
a mutable view of the transition function of this machine

getStartState

public java.lang.Object getStartState()
Returns a mutable view of the start state of this machine

Returns:
a mutable view of the start state of this machine

getAcceptStates

public java.util.Set getAcceptStates()
Returns a mutable view of the accept states of this machine. Note: Modifying this value can have an adverse affect on the instance of the class it was called on. Do so at your own risk!

Returns:
a mutable view of the accept states of this machine

toStateTable

public java.lang.String[][] toStateTable()
Returns a convenient view of this FiniteAutomata as a 2 dimensional array. Functionally very equivalent to TransitionFunction.toTable(), but with the added benefit of identifying the start state (with a →) and accept states are enclosed with asterixes.

Returns:
A Convenience view of this FiniteAutomata