laser.regularlanguage.fsa
Class AbstractRunnableFSA<L extends LabelInterface>

java.lang.Object
  extended by laser.regularlanguage.fsa.AbstractFSA<L>
      extended by laser.regularlanguage.fsa.AbstractRunnableFSA<L>
Type Parameters:
L - The type of Label associated with this FSA.
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, ArtifactInterface, FSAInterface<L>, RunnableFSAInterface<L>, Annotatable, Persistent, Visualizable
Direct Known Subclasses:
RunnableFSA

public abstract class AbstractRunnableFSA<L extends LabelInterface>
extends AbstractFSA<L>
implements RunnableFSAInterface<L>

An abstract class representing FSAs that are runnable.

NOTES:

The states must have IDs in the range from 0 to |Q| - 1.

The transitions must have IDs in the range from 0 to |T| - 1.

This class is not synchronized, and attempts to use it with non-sequential code may result in unexpected behavior.

Author:
Nathan A. Jokel (laser-software@cs.umass.edu)
See Also:
RunnableFSAInterface, Serialized Form

Field Summary
protected  AbstractFSATransitionTable<L> table
          An AbstractFSATransitionTable to which this runnable FSA can dispatch calls to computation methods.
 
Fields inherited from class laser.regularlanguage.fsa.AbstractFSA
_alphabet, _factory, _nextStateID, _nextTransitionID, _startState, _states, _transitionIndex, _transitions
 
Fields inherited from interface laser.util.Persistent
PER_EXTENSION, READ_PERSISTENT_METHOD_NAME
 
Constructor Summary
protected AbstractRunnableFSA(AbstractFSA<L> fsa, java.lang.Class<? extends AbstractFSATransitionTable> tableClass)
          Creates a new runnable FSA with the same states, transitions, and Alphabet as the specified FSA and an AbstractFSATransitionTable of the specified Class.
 
Method Summary
protected  void _checkBackwardsConfiguration(java.util.SortedSet<? extends FSAStateInterface<L>> states)
          Checks the given backwards configuration.
protected  void _checkConfiguration(java.util.SortedSet<? extends FSAStateInterface<L>> states)
          Checks the given configuration.
protected  void _checkForwardsConfiguration(java.util.SortedSet<? extends FSAStateInterface<L>> states)
          Checks the given forwards configuration.
 java.util.List<java.lang.String> checkWellFormed()
          Checks that this FSA is well-formed and returns a List of any well-formedness violitions if they exist.
abstract  RunnableFSAInterface<L> clone()
          Returns a copy of this runnable FSA.
 java.util.SortedSet<? extends FSAStateInterface<L>> getAcceptStates()
          Returns an unmodifiable view of the set A, the accept states of the FSA.
 MutableFSAInterface<L> getMutableFSA()
          Returns the mutable FSA corresponding to this runnable FSA.
 java.util.SortedSet<? extends FSAStateInterface<L>> getNonAcceptStates()
          Returns an unmodifiable view of the set QA, the non-accept states of this FSA.
protected  void initializeFields()
          A helper method for the constructors that initializes certain member fields.
 boolean isAcceptedStringBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states, java.util.List<? extends L> inputString)
          Returns true if this FSA accepts the specified input string when run backwards, false otherwise.
 boolean isAcceptedStringForwards(java.util.List<? extends L> inputString)
          Returns true if the FSA accepts the specified input string when run forwards, false otherwise.
 boolean isDeterministic()
          Returns true if this FSA is deterministic and false otherwise.
 boolean isFinalConfigurationBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
          Returns true if the given Set of states is accepting for this FSA, false otherwise.
 boolean isFinalConfigurationForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
          Returns true if the given Set of states is accepting for this FSA, false otherwise.
 boolean isTotal()
          Returns true if this FSA is total, false otherwise.
 java.util.SortedSet<? extends FSAStateInterface<L>> runBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states, L label)
          Runs this FSA backwards from the specified starting configuration, returning the reachable state(s) given the specified label (optional operation).
 java.util.SortedSet<? extends FSAStateInterface<L>> runBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states, java.util.List<? extends L> inputString)
          Runs this FSA backwards from the specified starting configuration, returning the reachable state(s) given the specified input string (optional operation).
 java.util.SortedSet<? extends FSAStateInterface<L>> runForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states, L label)
          Runs this FSA forwards from the specified starting configuration, returning the reachable state(s) given the specified label.
 java.util.SortedSet<? extends FSAStateInterface<L>> runForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states, java.util.List<? extends L> inputString)
          Runs this FSA forwards from the specified starting configuration, returning the reachable state(s) given the specified input string.
 boolean supportsLabelPatterns()
          Returns true if this FSA supports label patterns and false otherwise.
 boolean supportsRunningBackwards()
          Returns true if this FSA supports running backwards and false otherwise.
 
Methods inherited from class laser.regularlanguage.fsa.AbstractFSA
_checkLabel, _checkState, _checkTransition, _internalAddTransition, _internalCopyFSAAttributes, _internalRemoveState, _internalRemoveTransition, addAnnotation, addAnnotations, copyAnnotations, getAlphabet, getAnnotationClasses, getAnnotationClasses, getAnnotationFilters, getAnnotations, getAnnotations, getDescription, getDotWriter, getEpsilonTransition, getFactory, getName, getStartState, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, getVisExtension, hasTransitionsOnEpsilon, readPersistent, readPersistent, removeAnnotation, removeAnnotations, removeAnnotations, removeAnnotations, setAnnotationFilters, setDescription, setName, toDot, toDot, visualize, visualize, writePersistent, writePersistent
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface laser.regularlanguage.fsa.RunnableFSAInterface
getInitialConfigurationForwards
 
Methods inherited from interface laser.regularlanguage.fsa.FSAInterface
getAlphabet, getDescription, getEpsilonTransition, getFactory, getName, getStartState, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, hasTransitionsOnEpsilon, setDescription, setName, supportsEpsilonTransitions, supportsNondeterminism
 
Methods inherited from interface laser.util.Annotatable
addAnnotation, addAnnotations, copyAnnotations, getAnnotationClasses, getAnnotationClasses, getAnnotationFilters, getAnnotations, getAnnotations, removeAnnotation, removeAnnotations, removeAnnotations, removeAnnotations, setAnnotationFilters
 
Methods inherited from interface laser.util.Persistent
writePersistent, writePersistent
 
Methods inherited from interface laser.util.Visualizable
getVisExtension, visualize, visualize
 

Field Detail

table

protected final AbstractFSATransitionTable<L extends LabelInterface> table
An AbstractFSATransitionTable to which this runnable FSA can dispatch calls to computation methods.

Constructor Detail

AbstractRunnableFSA

protected AbstractRunnableFSA(AbstractFSA<L> fsa,
                              java.lang.Class<? extends AbstractFSATransitionTable> tableClass)
Creates a new runnable FSA with the same states, transitions, and Alphabet as the specified FSA and an AbstractFSATransitionTable of the specified Class.

PRECONDITIONS: fsa and tableClass are not null. AbstractFSATransitionTables of tableClass have a constructor that takes a single RunnableFSA parameter.

Note this constructor should only be called by the AbstractFSAFactory._internalGetRunnableFSA(laser.regularlanguage.fsa.MutableFSA) and RunnableFSA.clone() methods and by constructors of subclasses of this class.

Parameters:
fsa - The FSA.
tableClass - The class of AbstractFSATransitionTable to use.
Throws:
InconsistentObjectError - if there is a problem instantiating the transition table.
See Also:
AbstractFSAFactory._internalGetRunnableFSA(laser.regularlanguage.fsa.MutableFSA), clone()
Method Detail

_checkConfiguration

protected void _checkConfiguration(java.util.SortedSet<? extends FSAStateInterface<L>> states)
Checks the given configuration.

Parameters:
states - The configuration to be checked
Throws:
java.lang.IllegalArgumentException - if the configuration is null

_checkForwardsConfiguration

protected void _checkForwardsConfiguration(java.util.SortedSet<? extends FSAStateInterface<L>> states)
Checks the given forwards configuration.

Parameters:
states - The forwards configuration to be checked
Throws:
java.lang.IllegalArgumentException - if the configuration is null

_checkBackwardsConfiguration

protected void _checkBackwardsConfiguration(java.util.SortedSet<? extends FSAStateInterface<L>> states)
Checks the given backwards configuration.

Parameters:
states - The backwards configuration to be checked
Throws:
java.lang.IllegalArgumentException - if the configuration is null

initializeFields

protected void initializeFields()
A helper method for the constructors that initializes certain member fields.


clone

public abstract RunnableFSAInterface<L> clone()
Returns a copy of this runnable FSA.

Specified by:
clone in interface FSAInterface<L extends LabelInterface>
Specified by:
clone in class AbstractFSA<L extends LabelInterface>
Returns:
A copy of this runnable FSA.

getAcceptStates

public java.util.SortedSet<? extends FSAStateInterface<L>> getAcceptStates()
Returns an unmodifiable view of the set A, the accept states of the FSA.

NOTE: The returned SortedSet is unmodifiable.

Specified by:
getAcceptStates in interface FSAInterface<L extends LabelInterface>
Overrides:
getAcceptStates in class AbstractFSA<L extends LabelInterface>
Returns:
An unmodifiable view of the accept states of this FSA.

getMutableFSA

public MutableFSAInterface<L> getMutableFSA()
Returns the mutable FSA corresponding to this runnable FSA. No references are maintained between the FSAs, thus modifying the mutable FSA has no effect on the runnable FSA.

Specified by:
getMutableFSA in interface RunnableFSAInterface<L extends LabelInterface>
Returns:
The mutable FSA corresponding to this runnable FSA.

getNonAcceptStates

public java.util.SortedSet<? extends FSAStateInterface<L>> getNonAcceptStates()
Returns an unmodifiable view of the set QA, the non-accept states of this FSA.

NOTE: The returned SortedSet is unmodifiable.

Specified by:
getNonAcceptStates in interface FSAInterface<L extends LabelInterface>
Overrides:
getNonAcceptStates in class AbstractFSA<L extends LabelInterface>
Returns:
An unmodifiable view of the non-accepting states of this FSA.

isFinalConfigurationForwards

public boolean isFinalConfigurationForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
Returns true if the given Set of states is accepting for this FSA, false otherwise. That is, returns true iff (∃ qstates : qA).

PRECONDITIONS:

Specified by:
isFinalConfigurationForwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
states - The states to be tested.
Returns:
true if the given set of states is accepting for this FSA, false otherwise.
Throws:
java.lang.IllegalArgumentException - if states or any of its elements is null of any of its elements is not a part of this FSA.

isFinalConfigurationBackwards

public boolean isFinalConfigurationBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
Returns true if the given Set of states is accepting for this FSA, false otherwise. That is, returns true iff (q0states).

PRECONDITIONS:

Specified by:
isFinalConfigurationBackwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
states - The states to be tested.
Returns:
true if the given set of states is accepting for this FSA, false otherwise.
Throws:
java.lang.IllegalArgumentException - if states or any of its elements is null or any of its elements is not part of this FSA.

isAcceptedStringForwards

public boolean isAcceptedStringForwards(java.util.List<? extends L> inputString)
Returns true if the FSA accepts the specified input string when run forwards, false otherwise.

NOTE: The specified List may be empty, in which case the empty string is given as input.

PRECONDITIONS:

Specified by:
isAcceptedStringForwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
inputString - The input string being tested for acceptance.
Returns:
tt>true if the FSA accepts the specified input, false otherwise
Throws:
java.lang.IllegalArgumentException - if inputLabels or any of its elements is null or any of its elements is not contained in the alphabet of this FSA.

isAcceptedStringBackwards

public boolean isAcceptedStringBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states,
                                         java.util.List<? extends L> inputString)
Returns true if this FSA accepts the specified input string when run backwards, false otherwise.

NOTE: The specified List may be empty, in which case the empty string is given as input.

PRECONDITIONS:

Specified by:
isAcceptedStringBackwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
states - The initial configuration of this FSA before the first label Label in inputLabels is processed.
inputString - The input string being tested for acceptance.
Returns:
true if this FSA accepts the specified input, false otherwise
Throws:
java.lang.IllegalArgumentException - if inputLabels or any of its elements is null or any of its elements is not contained in the alphabet of this FSA.

isDeterministic

public boolean isDeterministic()
                        throws FSAInterfaceException
Returns true if this FSA is deterministic and false otherwise. If this FSA does not support nondeterminism, true will always be returned. If this FSA supports nondeterminism, true is returned only if this FSA has no epsilon (ε) transitions and no two transitions have the same source state and label. More formally, true is returned iff (∀ tT : label(t) ≠ ε) ∧ (∄ x, yT : xysource(x) = source(y) ∧ label(x) = label(y)). This takes into account any transitions in T specified by transitions on LabelPatterns.

Specified by:
isDeterministic in interface FSAInterface<L extends LabelInterface>
Overrides:
isDeterministic in class AbstractFSA<L extends LabelInterface>
Returns:
true if this FSA is deterministic and false otherwise.
Throws:
WellFormednessException - if the FSA is not well formed.
FSAInterfaceException - if the FSA is not well-formed.
See Also:
checkWellFormed()

isTotal

public boolean isTotal()
Returns true if this FSA is total, false otherwise. An FSA is total if all of its states have at least one outgoing transition on every Label in the FSA's Alphabet. Formally, an FSA is total iff (∀ l ∈ Σ, qQ : (∃ tT : source(t) = qlabel(t) = l)). This takes into account any transitions in T specified by transitions on LabelPatterns.

Specified by:
isTotal in interface FSAInterface<L extends LabelInterface>
Overrides:
isTotal in class AbstractFSA<L extends LabelInterface>
Returns:
true if this FSA is total, false otherwise.

checkWellFormed

public final java.util.List<java.lang.String> checkWellFormed()
Checks that this FSA is well-formed and returns a List of any well-formedness violitions if they exist.

Specified by:
checkWellFormed in interface FSAInterface<L extends LabelInterface>
Overrides:
checkWellFormed in class AbstractFSA<L extends LabelInterface>
Returns:
A List of the well-formedness violations if they exist and null otherwise

runForwards

public java.util.SortedSet<? extends FSAStateInterface<L>> runForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states,
                                                                       L label)
Runs this FSA forwards from the specified starting configuration, returning the reachable state(s) given the specified label.

Formally, call the given set of states states S, the given label l, and the returned set of states S'. S' = M U E where:

M = { q ∈ Q : (∃ t : (t ∈ T ∧ source(t) ∈ S ∧ label(t) = l ∧ target(t) = q)) }

E =

empty if this FSA does not support epsilon transitions

epsilonClosureForwards(M) otherwise

PRECONDITIONS:

Specified by:
runForwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
states - The states comprising the configuration of this FSA just before the given label is processed.
label - The Label that specifies the input symbol given to this FSA. All of the Labels must equal a Label contained in the Alphabet of the FSA.
Returns:
The reachable state(s) of the FSA after processing the specified label
Throws:
java.lang.IllegalArgumentException - if states or any element is null or any element is not a part of this FSA or if label is null or is not contained in the alphabet of this FSA.
See Also:
The definition of epsilonClosureForwards

runForwards

public java.util.SortedSet<? extends FSAStateInterface<L>> runForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states,
                                                                       java.util.List<? extends L> inputString)
Runs this FSA forwards from the specified starting configuration, returning the reachable state(s) given the specified input string.

NOTE: The specified List may be empty, in which case the empty string is given as input.

Formally, call the returned set of states S. It is defined as follows:

inputLabels specifies the input string l1, l2, … , lm.
(∀ qQ : qS ↔ (∃ t1, t2, …, tn : (∀ 1 ≤ in : tiTsource(t1) ∈ statestarget(tm) = q ∧ (∀ 1 ≤ j < n : target(tj) = source(tj + 1)) ∧ label(t1), label(t2), …, label(tn) |Σ = l1, l2, …, lm))).

PRECONDITIONS:

Specified by:
runForwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
states - The states comprising the configuration of this FSA just before the first Label in inputLabels is processed.
inputString - The list of Labels that specifies the input string given to this FSA. All of the Labels must equal a Label contained in the Alphabet of the FSA.
Returns:
The reachable state(s) of the FSA after processing all of the specified input.
Throws:
java.lang.IllegalArgumentException - if states or any element is null or any element is not a part of this FSA or if inputString or any element is null or any element is not contained in the alphabet of this FSA.

runBackwards

public java.util.SortedSet<? extends FSAStateInterface<L>> runBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states,
                                                                        L label)
Runs this FSA backwards from the specified starting configuration, returning the reachable state(s) given the specified label (optional operation).

Formally, call the given set of states states S, the given label l, and the returned set of states S'. S' = M U E where:

M = { q ∈ Q : (∃ t : (t ∈ T ∧ source(t) = q ∧ label(t) = l ∧ target(t) ∈ S)) }

E =

empty if this FSA does not support epsilon transitions

epsilonClosureBackwards(M) otherwise

PRECONDITIONS:

Specified by:
runBackwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
states - The states comprising the configuration of this FSA just before the given label is processed.
label - The Label that specifies the input symbol given to this FSA. All of the Labels must equal a Label contained in the Alphabet of the FSA.
Returns:
The reachable state(s) of the FSA after processing the specified label
Throws:
java.lang.IllegalArgumentException - if states or any element is null or any element is not a part of this FSA or if label is null or is not contained in the alphabet of this FSA.
java.lang.UnsupportedOperationException - if this method is not supported.
See Also:
The definition of epsilonClosureBackwards

runBackwards

public java.util.SortedSet<? extends FSAStateInterface<L>> runBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states,
                                                                        java.util.List<? extends L> inputString)
Runs this FSA backwards from the specified starting configuration, returning the reachable state(s) given the specified input string (optional operation).

NOTE: The specified List may be empty, in which case the empty string is given as input.

Formally, call the returned set of states S. It is defined as follows:

inputLabels specifies the input string l1, l2, … , lm.
(∀ qQ : qS ↔ (∃ t1, t2, …, tn : (∀ 1 ≤ in : tiTsource(t1) = qtarget(tm) = ∈ states ∧ (∀ 1 ≤ j < n : target(tj) = source(tj + 1)) ∧ label(t1), label(t2), …, label(tn) |Σ = l1, l2, …, lm))).

PRECONDITIONS:

Specified by:
runBackwards in interface RunnableFSAInterface<L extends LabelInterface>
Parameters:
states - The states comprising the configuration of this FSA before the first label Label in inputLabels is processed.
inputString - The list of Labels that specifies the input string given to this FSA. All of the Labels must equal a Label contained in the Alphabet of the FSA.
Returns:
The reachable state(s) of the FSA after processing all of the specified input.
Throws:
java.lang.IllegalArgumentException - if states or any element is null or any element is not a part of this FSA or if inputString or any element is null or any element is not contained in the alphabet of this FSA.
java.lang.UnsupportedOperationException - if this method is not supported.

supportsLabelPatterns

public boolean supportsLabelPatterns()
Returns true if this FSA supports label patterns and false otherwise.

More formally, returns label is defined to include P.

Returns:
True if label patterns are supported and false otherwise

supportsRunningBackwards

public boolean supportsRunningBackwards()
Returns true if this FSA supports running backwards and false otherwise.

Specified by:
supportsRunningBackwards in interface RunnableFSAInterface<L extends LabelInterface>
Returns:
True if running backwards is supported and false otherwise