laser.regularlanguage.fsa
Interface FSAInterface<L extends LabelInterface>

Type Parameters:
L - The type of Label associated with this FSA.
All Superinterfaces:
Annotatable, ArtifactInterface, java.lang.Cloneable, Persistent, java.io.Serializable, Visualizable
All Known Subinterfaces:
DFAInterface<L>, MutableDFAInterface<L>, MutableFSAInterface<L>, RunnableDFAInterface<L>, RunnableFSAInterface<L>
All Known Implementing Classes:
AbstractFSA, AbstractMutableFSA, AbstractRunnableFSA, MutableDFA, MutableFSA, RunnableDFA, RunnableFSA

public interface FSAInterface<L extends LabelInterface>
extends Annotatable, ArtifactInterface, java.lang.Cloneable

An FSA is a finite state automaton. This interface is implemented by different types of FSAs. An FSA is defined as an 8-tuple:

(Q, Σ, q0, A, T, source, target, label)

If the FSA supports epsilon transitions then label is defined to include epsilon (ε) otherwise it is defined to exclude epsilon (ε). See supportsEpsilonTransitions().

If the FSA supports non-determinism then FSAStateInterface#getOutgoingTransitions(L) is defined to return zero or more transitions otherwise it is defined to return zero or one transitions. See supportsNondeterminism().

It is possible to define special cases of FSAs by loosening the above definition or by placing restrictions on the above definition. An example is DFAInterface.

Classes implementing FSAInterface should only be instantiated via the appropriate factory methods, never directly by their constructors. This is a factory as in the design pattern, (Design Patterns, Gamma, Helm, Johnson,and Vlissides, pp 87, 107, 1995).

Author:
Nathan Jokel (laser-software@cs.umass.edu)
See Also:
AlphabetInterface, LabelInterface, FSAStateInterface, FSATransitionInterface, FSAFactoryInterface

Field Summary
 
Fields inherited from interface laser.util.Persistent
PER_EXTENSION, READ_PERSISTENT_METHOD_NAME
 
Method Summary
 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.
 FSAInterface<L> clone()
          Returns a copy of this FSA.
 java.util.SortedSet<? extends FSAStateInterface<L>> getAcceptStates()
          Returns the set A, the accept states of the FSA.
 AlphabetInterface<L> getAlphabet()
          Returns the alphabet, Σ, of this FSA.
 java.lang.StringBuffer getDescription()
          Returns the description of this FSA or null if one has not been specified.
 FSAEpsilonTransitionInterface<L> getEpsilonTransition(FSAStateInterface<L> source, FSAStateInterface<L> target)
          Returns the transition from the specified source state to the specified target state on epsilon (ε) if one exists in the FSA, otherwise null is returned (optional operation).
 FSAFactoryInterface<L> getFactory()
          Returns a reference to a factory that creates FSAs of this type.
 java.lang.String getName()
          Returns the name of this FSA, or null if one has not been specified.
 java.util.SortedSet<? extends FSAStateInterface<L>> getNonAcceptStates()
          Returns the non-accept states of the FSA, QA.
 FSAStateInterface<L> getStartState()
          Returns the start state, q0, of the FSA.
 java.util.SortedSet<? extends FSAStateInterface<L>> getStates()
          Returns the set Q, the states of the FSA.
 FSAStateInterface<L> getStateWithID(int id)
          Returns the state of this FSA with the specified id number.
 FSALabelTransitionInterface<L> getTransition(FSAStateInterface<L> source, L label, FSAStateInterface<L> target)
          Returns the transition from the specified source state to the specified target state on an equal Label to the given Label if one exists in the FSA, otherwise null is returned.
 java.util.SortedSet<? extends FSATransitionInterface<L>> getTransitions()
          Returns the set T, the transitions of the FSA.
 java.util.SortedSet<? extends FSATransitionInterface<L>> getTransitions(FSAStateInterface<L> source, FSAStateInterface<L> target)
          Returns a non-null Set containing all the transitions from the specified source to the given target state.
 FSATransitionInterface<L> getTransitionWithID(int id)
          Returns the transition of this FSA with the specified id number.
 boolean hasTransitionsOnEpsilon()
          Returns true if this FSA has any transitions on epsilon, false otherwise (optional operation).
 boolean isDeterministic()
          Returns true if this FSA is deterministic and false otherwise.
 boolean isTotal()
          Returns true if this FSA is total, false otherwise.
 void setDescription(java.lang.StringBuffer description)
          Sets the description of this FSA to a copy of the specified StringBuffer.
 void setName(java.lang.String name)
          Sets the name of this FSA to the specified String.
 boolean supportsEpsilonTransitions()
          Returns true if this FSA supports epsilon transitions and false otherwise.
 boolean supportsNondeterminism()
          Returns true if this FSA supports nondeterminism and false otherwise.
 
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
 

Method Detail

clone

FSAInterface<L> clone()
Returns a copy of this FSA.

Returns:
A copy of this FSA.

getAcceptStates

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

NOTE: Modifying the returned set of states will not affect this FSA.

Returns:
The accept states of this FSA.

getAlphabet

AlphabetInterface<L> getAlphabet()
Returns the alphabet, Σ, of this FSA.

NOTE: Modifying the returned AlphabetInterface will not affect the alphabet of this FSA.

Returns:
The alphabet of this FSA.

getFactory

FSAFactoryInterface<L> getFactory()
Returns a reference to a factory that creates FSAs of this type.

Returns:
a reference to a factory that creates FSAs of this type.

getDescription

java.lang.StringBuffer getDescription()
Returns the description of this FSA or null if one has not been specified.

NOTE: Modifying the returned StringBuffer will not affect the description of the FSA.

Returns:
The description of this FSA or null if one has not been specified.

getEpsilonTransition

FSAEpsilonTransitionInterface<L> getEpsilonTransition(FSAStateInterface<L> source,
                                                      FSAStateInterface<L> target)
Returns the transition from the specified source state to the specified target state on epsilon (ε) if one exists in the FSA, otherwise null is returned (optional operation). More formally, returns (tT : source(t) = sourcetarget(t) = targetlabel(t) = ε) or null if no such t exists.

If this FSA does not support epsilon (ε) transitions, this method should not be supported. An UnsupportedOperationException may be thrown depending on the implementation.

PRECONDITIONS:

Parameters:
source - The source state.
target - The target state.
Returns:
The epsilon transition if it exists, null otherwise.
Throws:
java.lang.IllegalArgumentException - if source/target is null or is not a part of this FSA.
java.lang.UnsupportedOperationException - if this FSA does not support epsilon (ε) transitions

getName

java.lang.String getName()
Returns the name of this FSA, or null if one has not been specified.

Returns:
The name of this FSA, or null if one has not been specified.

getNonAcceptStates

java.util.SortedSet<? extends FSAStateInterface<L>> getNonAcceptStates()
Returns the non-accept states of the FSA, QA.

NOTE: Modifying the returned set of states will not affect this FSA.

Returns:
The non-accept states of the FSA.

getStartState

FSAStateInterface<L> getStartState()
Returns the start state, q0, of the FSA.

Returns:
The start state of this FSA

getStates

java.util.SortedSet<? extends FSAStateInterface<L>> getStates()
Returns the set Q, the states of the FSA.

NOTE: Modifying the returned set of states will not affect this FSA.

Returns:
The set Q, the states of the FSA.

getStateWithID

FSAStateInterface<L> getStateWithID(int id)
Returns the state of this FSA with the specified id number. If no such state exists, null is returned.

Parameters:
id - The id number of the state to be returned.
Returns:
The state with the specified id number.

getTransition

FSALabelTransitionInterface<L> getTransition(FSAStateInterface<L> source,
                                             L label,
                                             FSAStateInterface<L> target)
Returns the transition from the specified source state to the specified target state on an equal Label to the given Label if one exists in the FSA, otherwise null is returned. More formally, returns (tT : source(t) = sourcetarget(t) = targetlabel(t) = label) or null if no such t exists.

PRECONDITIONS:

Parameters:
source - The source state.
label - The Label of the transition.
target - The target state.
Returns:
The transition if it exists, null otherwise.
Throws:
java.lang.IllegalArgumentException - if source/target is null or is not part of this FSA or label is null or is not contained in the alphabet of this FSA.

getTransitions

java.util.SortedSet<? extends FSATransitionInterface<L>> getTransitions()
Returns the set T, the transitions of the FSA.

NOTE: Modifying the returned set of transitions will not affect this FSA.

Returns:
The set T, the transitions of the FSA.

getTransitions

java.util.SortedSet<? extends FSATransitionInterface<L>> getTransitions(FSAStateInterface<L> source,
                                                                        FSAStateInterface<L> target)
Returns a non-null Set containing all the transitions from the specified source to the given target state. Formally, returns the set S where (∀ tT : tSsource(t) = sourcetarget(t) = target).

NOTE: Modifying the returned set of transitions will not affect this FSA.

PRECONDITIONS:

Parameters:
source - The source state.
target - The target state.
Returns:
A non-null Set containing all the transitions from the specified source to the given target state.

Throws:
java.lang.IllegalArgumentException - if source/target is null or is not a part of this FSA.

getTransitionWithID

FSATransitionInterface<L> getTransitionWithID(int id)
Returns the transition of this FSA with the specified id number. If no such transition exists, null is returned.

Parameters:
id - The id number of the transition to be returned.
Returns:
The transition with the specified id number.

hasTransitionsOnEpsilon

boolean hasTransitionsOnEpsilon()
Returns true if this FSA has any transitions on epsilon, false otherwise (optional operation). More formally, returns true iff (∃ t ∈ T : label(t) = ε).

NOTE: This FSA may support transitions on epsilon but not actually contain any transition on epsilon.

If this FSA does not support transitions on epsilon, calling this method may cause an UnsupportedOperationException to be thrown, depending on the implementation.

Returns:
true if this FSA has any transitions on epsilon, false otherwise.
Throws:
java.lang.UnsupportedOperationException - this FSA does not support transitions on epsilon.

isDeterministic

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 : source(x) = source(y) ∧ label(x) = label(y) → x = y).

Returns:
true if this FSA is deterministic and false otherwise.
Throws:
FSAInterfaceException - if the FSA is not well-formed.
See Also:
checkWellFormed()

isTotal

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)).

Returns:
true if this FSA is total, false otherwise.

checkWellFormed

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.

Returns:
A List of the well-formedness violations if they exist and null otherwise

setDescription

void setDescription(java.lang.StringBuffer description)
Sets the description of this FSA to a copy of the specified StringBuffer.

NOTE: No references are maintained between the given StringBuffer and the description of the FSA, thus modifying the given StringBuffer after the method returns has no effect on the description.

Parameters:
description - The StringBuffer.

setName

void setName(java.lang.String name)
Sets the name of this FSA to the specified String.

Parameters:
name - The String.

supportsEpsilonTransitions

boolean supportsEpsilonTransitions()
Returns true if this FSA supports epsilon transitions and false otherwise.

Returns:
True if epsilon transitions are supported and false otherwise

supportsNondeterminism

boolean supportsNondeterminism()
Returns true if this FSA supports nondeterminism and false otherwise.

Returns:
True if nondeterminism is supported and false otherwise