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

java.lang.Object
  extended by laser.regularlanguage.fsa.AbstractFSA<L>
      extended by laser.regularlanguage.fsa.AbstractMutableFSA<L>
          extended by laser.regularlanguage.fsa.MutableFSA<L>
              extended by laser.regularlanguage.fsa.MutableDFA<L>
Type Parameters:
L - The type of Label associated with this FSA.
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, ArtifactInterface, DFAInterface<L>, FSAInterface<L>, MutableDFAInterface<L>, MutableFSAInterface<L>, Annotatable, Persistent, Visualizable

public class MutableDFA<L extends LabelInterface>
extends MutableFSA<L>
implements MutableDFAInterface<L>

This class represents DFAs that are mutable.

Note that 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:
MutableDFAInterface, Serialized Form

Field Summary
 
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
 
Fields inherited from interface laser.util.Persistent
PER_EXTENSION, READ_PERSISTENT_METHOD_NAME
 
Constructor Summary
protected MutableDFA(AlphabetInterface<L> alphabet, AbstractFSAFactory<L> factory)
          Returns a new MutableDFA with the specified Alphabet and factory.
protected MutableDFA(MutableDFA<L> dfa)
          Creates a new MutableDFA with the same states, transitions, and Alphabet as the specified MutableDFA (copy constructor).
protected MutableDFA(RunnableDFA<L> dfa)
          Returns the mutable DFA corresponding to the specified runnable DFA.
 
Method Summary
 FSAEpsilonTransitionInterface<L> addEpsilonTransition(FSAStateInterface<L> source, FSAStateInterface<L> target, java.lang.Object... args)
          DFAs do not support epsilon (ε) transitions.
 FSALabelPatternTransitionInterface<L> addTransition(FSAStateInterface<L> source, LabelPatternInterface<L> labelPattern, FSAStateInterface<L> target, java.lang.Object... args)
          Adds a transition to this FSA from the specified source state to the specified target state on the given LabelPattern and returns a reference to the newly created transition.
 FSALabelTransitionInterface<L> addTransition(FSAStateInterface<L> source, L label, FSAStateInterface<L> target, java.lang.Object... args)
          Adds a transition to this FSA from the specified source state to the specified target state on the given Label, and returns a reference to the newly created transition.
 java.util.List<java.lang.String> checkWellFormed()
          Returns true if this FSA is well-formed, false otherwise.
 MutableDFA<L> clone()
          Returns a copy of this mutable DFA.
 FSAEpsilonTransitionInterface<L> getEpsilonTransition(FSAStateInterface<L> source, FSAStateInterface<L> target)
          DFAs do not support epsilon (ε) transitions.
 RunnableDFAInterface<L> getRunnableFSA()
          Returns the runnable FSA corresponding to this mutable FSA.
 boolean hasTransitionsOnEpsilon()
          DFAs do not support epsilon (ε) transitions.
 boolean isDeterministic()
          Returns true
 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 class laser.regularlanguage.fsa.AbstractMutableFSA
_checkLabelPattern, addLabel, addLabels, addState, addTransitions, copy, copyFSAAttributes, copyState, copyTransition, deleteDeadStates, deleteUnreachableStates, getCreateArgsForLabelTransition, getCreateArgsForTrapState, getCreateArgsForTrapTransition, getLabelPatterns, getStartState, getTransition, hasTransitionsOnLabelPatterns, makeTotal, removeLabel, removeLabels, removeState, removeTransition, removeTransitions, replaceLabelPatternTransitionsWithLabelTransitions, setAlphabet, setStartState, supportsLabelPatterns
 
Methods inherited from class laser.regularlanguage.fsa.AbstractFSA
_checkLabel, _checkState, _checkTransition, _internalAddTransition, _internalCopyFSAAttributes, _internalRemoveState, _internalRemoveTransition, addAnnotation, addAnnotations, copyAnnotations, getAcceptStates, getAlphabet, getAnnotationClasses, getAnnotationClasses, getAnnotationFilters, getAnnotations, getAnnotations, getDescription, getDotWriter, getFactory, getName, getNonAcceptStates, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, getVisExtension, isTotal, 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.FSAInterface
getAcceptStates, getAlphabet, getDescription, getFactory, getName, getNonAcceptStates, getStartState, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, isTotal, setDescription, setName
 
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
 
Methods inherited from interface laser.regularlanguage.fsa.MutableFSAInterface
addLabel, addLabels, addState, addTransitions, copy, copyFSAAttributes, copyState, copyTransition, deleteDeadStates, deleteUnreachableStates, getLabelPatterns, getTransition, hasTransitionsOnLabelPatterns, makeTotal, removeLabel, removeLabels, removeState, removeTransition, removeTransitions, replaceLabelPatternTransitionsWithLabelTransitions, setAlphabet, setStartState, supportsLabelPatterns
 
Methods inherited from interface laser.regularlanguage.fsa.FSAInterface
getAcceptStates, getAlphabet, getDescription, getFactory, getName, getNonAcceptStates, getStartState, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, isTotal, setDescription, setName
 
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
 

Constructor Detail

MutableDFA

protected MutableDFA(AlphabetInterface<L> alphabet,
                     AbstractFSAFactory<L> factory)
Returns a new MutableDFA with the specified Alphabet and factory. The factory is used to create states and transitions and to get the runnable DFA corresponding to this mutable DFA.

PRECONDITIONS:

Note this constructor should only be called by the AbstractFSAFactory._internalCreateMutableDFAInterface(laser.alphabet.AlphabetInterface, laser.regularlanguage.fsa.AbstractFSAFactory) method and by constructors of subclasses of this class.

Parameters:
alphabet - The Alphabet.
factory - The factory
See Also:
AbstractFSAFactory._internalCreateMutableDFAInterface(laser.alphabet.AlphabetInterface, laser.regularlanguage.fsa.AbstractFSAFactory)

MutableDFA

protected MutableDFA(RunnableDFA<L> dfa)
Returns the mutable DFA corresponding to the specified runnable DFA.

PRECONDITION: The dfa is not null.

Note this constructor should only be called by the RunnableDFA.getMutableFSA() method.

Parameters:
dfa - The runnable DFA.
See Also:
RunnableDFA.getMutableFSA()

MutableDFA

protected MutableDFA(MutableDFA<L> dfa)
Creates a new MutableDFA with the same states, transitions, and Alphabet as the specified MutableDFA (copy constructor).

Precondition: dfa is not null.

Note this constructor should only be called by the clone() method.

Parameters:
dfa - The mutable DFA.
See Also:
clone()
Method Detail

clone

public MutableDFA<L> clone()
Returns a copy of this mutable DFA.

Specified by:
clone in interface FSAInterface<L extends LabelInterface>
Overrides:
clone in class MutableFSA<L extends LabelInterface>
Returns:
A copy of this mutable DFA.

addEpsilonTransition

public FSAEpsilonTransitionInterface<L> addEpsilonTransition(FSAStateInterface<L> source,
                                                             FSAStateInterface<L> target,
                                                             java.lang.Object... args)
DFAs do not support epsilon (ε) transitions. This method is not supported. Calling this method will cause an UnsupportedOperationException to be thrown.

Specified by:
addEpsilonTransition in interface MutableFSAInterface<L extends LabelInterface>
Overrides:
addEpsilonTransition in class MutableFSA<L extends LabelInterface>
Parameters:
source - The source state of the transition to be added.
target - The target state of the transition to be added.
args - Implementation specific arguments used to create the transition (optional).
Returns:
A reference to the epsilon (ε) transition.
Throws:
java.lang.UnsupportedOperationException - this FSA does not support epsilon (ε) transitions.

addTransition

public FSALabelTransitionInterface<L> addTransition(FSAStateInterface<L> source,
                                                    L label,
                                                    FSAStateInterface<L> target,
                                                    java.lang.Object... args)
Adds a transition to this FSA from the specified source state to the specified target state on the given Label, and returns a reference to the newly created transition. More formally, adds a transition t to T such that source(t) = sourcetarget(t) = targetlabel(t) = label.

If the same source state, Label, and target state are specified as a transition that already exists in the FSA, a reference to that transition is returned and the FSA remains unchanged.

A copy of the Label is used, thus no references are maintained between the specified Label and the Label on the transition, thus modifying the specified Label has no effect on the Label on the transition and vice versa.

DFAs do not support nondeterminism, thus there can only be exactly one transition with a certain source state and Label. Attempting to add a transition with the same source state and Label but a different target state as an existing transition will result in an FSAInterfaceException being thrown. This condition is formally specified as (∃ t'T : source(t') = sourcetarget(t') ≠ targetlabel(t') = label. Instead, the existing transition should first be removed using the AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface) method.

PRECONDITIONS:

Specified by:
addTransition in interface MutableFSAInterface<L extends LabelInterface>
Overrides:
addTransition in class MutableFSA<L extends LabelInterface>
Parameters:
source - The source state of the transition to be added.
label - The Label of the transition to be added.
target - The target state of the transition to be added.
args - Implementation specific arguments used to create the transition (optional).
Returns:
A reference to the transition.
Throws:
java.lang.IllegalArgumentException - if source/target is null or is not a state in this FSA, if label is null or is not contained in the alphabet of this FSA, or if invalid arguments are specified by args
java.lang.UnsupportedOperationException - a transition with the same source and Label as the specified source and Label but a different target already exists in the FSA (i.e. non-determinism would be introduced).
See Also:
AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface), AbstractFSAFactory._createFSALabelTransitionInterface(int, laser.regularlanguage.fsa.FSAStateInterface, L, laser.regularlanguage.fsa.FSAStateInterface, java.lang.Object...)

addTransition

public FSALabelPatternTransitionInterface<L> addTransition(FSAStateInterface<L> source,
                                                           LabelPatternInterface<L> labelPattern,
                                                           FSAStateInterface<L> target,
                                                           java.lang.Object... args)
Adds a transition to this FSA from the specified source state to the specified target state on the given LabelPattern and returns a reference to the newly created transition. This is equivalent to adding a set of transitions to T containing transitions from source to target on each of the Labels in the Alphabet of the FSA matched by the LabelPattern. This set may change if the Alphabet of the FSA changes, thus changing the set of Labels matched by the LabelPattern. More formally, call the transition on the LabelPattern being added p:
(∃ Sp : (∀ x ∈ Σ : xSp iff the LabelPattern on p matches x with respect to Σ) ∧ (∀ lSp : (∃ tT : source(t) = sourcetarget(t) = targetlabel(t) = l)))

This may introduce nondeterminism if a transition exists or is later added to the FSA with the same source state and a different target state on a Label that is matched by the LabelPattern or another LabelPattern that matches a common Label with the specified LabelPattern. Nondeterminism may also be introduced if the Alphabet of the FSA is subsequently changed, thus changing the set of Labels matched by the LabelPattern. DFAs do not support nondeterminism, thus this would cause the FSA to be not well-formed.

If the same source state, LabelPattern, and target state are specified as a transition that already exists in the FSA, a reference to that transition is returned and the FSA remains unchanged.

A copy of the LabelPattern is used, thus no references are maintained between the specified LabelPattern and the LabelPattern on the transition, thus modifying the specified LabelPattern has no effect on the LabelPattern on the transition and vice versa.

DFAs do not support nondeterminism, thus attempting to add a transition with the same source state and an equal LabelPattern but a different target state as an existing transition will definitely result in nondeterminism, thus an FSAInterfaceException will be thrown. Instead, the existing transition should first be removed using the AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface) method.

PRECONDITIONS:

Specified by:
addTransition in interface MutableFSAInterface<L extends LabelInterface>
Overrides:
addTransition in class MutableFSA<L extends LabelInterface>
Parameters:
source - The source state of the transition to be added.
labelPattern - The LabelPattern of the transition to be added.
target - The target state of the transition to be added.
args - Implementation specific arguments used to create the transition (optional).
Returns:
A refernce to the transition.
Throws:
java.lang.IllegalArgumentException - if source/target is null or is not a state in this FSA, if labelPattern is null or is not valid, if invalid arguments are specified by args, or if adding the transition would violate some well-formedness condition of this FSA.
java.lang.UnsupportedOperationException - a transition with the same source and LabelPattern as the specified source and LabelPattern but a different target already exists in the FSA (i.e. non-determinism would be introduced).
See Also:
laser.alphabetinterface.labelpatterninterface.LabelPatternInterface, AbstractMutableFSA.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface), FSAInterface.checkWellFormed(), AbstractFSAFactory._createFSALabelPatternTransitionInterface(int, laser.regularlanguage.fsa.FSAStateInterface, laser.alphabet.labelpattern.LabelPatternInterface, laser.regularlanguage.fsa.FSAStateInterface, java.lang.Object...)

getEpsilonTransition

public FSAEpsilonTransitionInterface<L> getEpsilonTransition(FSAStateInterface<L> source,
                                                             FSAStateInterface<L> target)
DFAs do not support epsilon (ε) transitions. This method is not supported. Calling this method will cause an UnsupportedOperationException to be thrown.

Specified by:
getEpsilonTransition in interface FSAInterface<L extends LabelInterface>
Overrides:
getEpsilonTransition in class AbstractFSA<L extends LabelInterface>
Parameters:
source - The source state.
target - The target state.
Returns:
The epsilon transition if it exists, null otherwise.
Throws:
java.lang.UnsupportedOperationException - this FSA does not support epsilon (ε) transitions.

getRunnableFSA

public RunnableDFAInterface<L> getRunnableFSA()
                                                              throws FSAInterfaceException
Returns the runnable FSA corresponding to this mutable FSA. This FSA must be well-formed. Any transitions on LabelPatterns are replaced with the corresponding transitions on Labels in the runnable FSA since a runnable FSA can not have transitions on LabelPatterns, but the mutable FSA remains unchanged. The states and transitions in the runnable FSA are reindexed, therefore the ID of a state or transition in the mutable FSA might not equal the ID of its corresponding state or transition in the runnable FSA.

No references are maintained between the FSAs, thus modifying the mutable FSA has no effect on the runnable FSA.

Specified by:
getRunnableFSA in interface MutableFSAInterface<L extends LabelInterface>
Overrides:
getRunnableFSA in class MutableFSA<L extends LabelInterface>
Returns:
The runnable FSA corresponding to this mutable FSA.
Throws:
WellFormednessException - if this FSA is not well-formed.
FSAInterfaceException - if this FSA is not well-formed.
See Also:
RunnableFSAInterface, FSAInterface.checkWellFormed(), AbstractMutableFSA.replaceLabelPatternTransitionsWithLabelTransitions()

hasTransitionsOnEpsilon

public boolean hasTransitionsOnEpsilon()
DFAs do not support epsilon (ε) transitions. This method is not supported. Calling this method will cause an UnsupportedOperationException to be thrown.

Specified by:
hasTransitionsOnEpsilon in interface FSAInterface<L extends LabelInterface>
Overrides:
hasTransitionsOnEpsilon in class AbstractFSA<L extends LabelInterface>
Returns:
true if this FSA has any transitions on epsilon, false otherwise.
Throws:
java.lang.UnsupportedOperationException - this FSA does not support epsilon (ε) transitions.

isDeterministic

public boolean isDeterministic()
                        throws FSAInterfaceException
Returns true

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

checkWellFormed

public java.util.List<java.lang.String> checkWellFormed()
Returns true if this FSA is well-formed, false otherwise.

The FSA must have a valid start state to be well-formed.

DFAs do not support nondeterminism, thus the FSA is not well-formed if any nondeterminism has been introduced by transitions on LabelPatterns - the LabelPatterns specify one or more transitions in T that cause two transitions in T to have the same source state and label; i.e.
(∃ x, yT : xysource(x) = source(y) ∧ label(x) = label(y))

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

supportsEpsilonTransitions

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

NOTE: By the DFA definition, this method always returns false.

Specified by:
supportsEpsilonTransitions in interface FSAInterface<L extends LabelInterface>
Overrides:
supportsEpsilonTransitions in class MutableFSA<L extends LabelInterface>
Returns:
True if epsilon transitions are supported and false otherwise

supportsNondeterminism

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

NOTE: By the DFA definition, this method always returns false.

Specified by:
supportsNondeterminism in interface FSAInterface<L extends LabelInterface>
Overrides:
supportsNondeterminism in class MutableFSA<L extends LabelInterface>
Returns:
True if nondeterminism is supported and false otherwise