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

q₀∈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