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

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

public interface RunnableFSAInterface<L extends LabelInterface>
extends FSAInterface<L>

This class represents FSAs that are runnable: i.e. computation can be performed on them but their structure can not be changed. A runnable FSA is always well-formed by construction. It can generate its corresponding mutable FSA at any time.

The definition of computation on an FSA is as follows:
The FSA must be given an input string. The input string is represented by a List. An input string is defined as a finite sequence of Labels l1, l2, … , lm such that (∀ 1 ≤ im : li ∈ Σ). The FSA can either accept or reject a given input string. An FSA accepts a given input string iff (∃ t1, t2, …, tn : (∀ 1 ≤ in : tiTsource(t1) = q0target(tn) ∈ F ∧ (∀ 1 ≤ j < n : target(tj) = source(tj + 1)) ∧ label(t1), label(t2), …, label(tn) |Σ = l1, l2, …, lm)).

DEFINITIONS:

Given S ⊆ Q.

Define S' as epsilonClosureForwards(S) as follows:

(∀ qQ : qS' ↔ (∃ t1, t2, …, tn : (∀ 1 ≤ in : tiTsource(t1) ∈ Starget(tn) = qlabel (ti) = ε ∧ (∀ 1 ≤ j < n : target(tj) = source (tj + 1)))))

Define S' as epsilonClosureBackwards(S) as follows:

(∀ qQ : qS' ↔ (∃ t1, t2, …, tn : (∀ 1 ≤ in : tiTtarget(t1) ∈ Ssource(tn) = qlabel (ti) = ε ∧ (∀ 1 ≤ j < n : source(tj) = target (tj + 1)))))

Author:
Nathan Jokel (laser-software@cs.umass.edu)
See Also:
FSAInterface, MutableFSAInterface

Field Summary
 
Fields inherited from interface laser.util.Persistent
PER_EXTENSION, READ_PERSISTENT_METHOD_NAME
 
Method Summary
 java.util.SortedSet<? extends FSAStateInterface<L>> getInitialConfigurationForwards()
          Returns the SortedSet of states in the initial configuration of this FSA.
 MutableFSAInterface<L> getMutableFSA()
          Returns the mutable FSA corresponding to this runnable FSA.
 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 this FSA accepts the specified input string when run forwards, false otherwise.
 boolean isFinalConfigurationBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
          Returns true if the given Set of states is a final configuration of this FSA, false otherwise (optional operation).
 boolean isFinalConfigurationForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
          Returns true if the given Set of states is a final configuration of this FSA, 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 supportsRunningBackwards()
          Returns true if this FSA supports running backwards and false otherwise.
 
Methods inherited from interface laser.regularlanguage.fsa.FSAInterface
checkWellFormed, clone, getAcceptStates, getAlphabet, getDescription, getEpsilonTransition, getFactory, getName, getNonAcceptStates, getStartState, getStates, getStateWithID, getTransition, getTransitions, getTransitions, getTransitionWithID, hasTransitionsOnEpsilon, isDeterministic, isTotal, 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
 

Method Detail

getInitialConfigurationForwards

java.util.SortedSet<? extends FSAStateInterface<L>> getInitialConfigurationForwards()
Returns the SortedSet of states in the initial configuration of this FSA.

Formally, call the returned set of states S. S = {q0} ∪ E where E =

the empty set if this FSA does not support epsilon transitions

epsilonClosureForwards({q0}) otherwise

Returns:
a SortedSet containing the states in the initial configuration of this FSA
See Also:
The definition of epsilonClosureForwards

getMutableFSA

MutableFSAInterface<L> getMutableFSA()
Returns the mutable FSA corresponding to this runnable FSA.

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

Returns:
The mutable FSA corresponding to this runnable FSA.

isFinalConfigurationForwards

boolean isFinalConfigurationForwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
Returns true if the given Set of states is a final configuration of this FSA, false otherwise.

Formally, returns true iff (∃ qstates : qA).

PRECONDITIONS:

Parameters:
states - The states to be tested.
Returns:
true if the given set of states is a final configuration of 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

boolean isFinalConfigurationBackwards(java.util.SortedSet<? extends FSAStateInterface<L>> states)
Returns true if the given Set of states is a final configuration of this FSA, false otherwise (optional operation).

Formally, returns true iff (q0states).

PRECONDITIONS:

Parameters:
states - The states to be tested.
Returns:
true if the given set of states is a final configuration of 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

boolean isAcceptedStringForwards(java.util.List<? extends L> inputString)
Returns true if this 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:

Parameters:
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.

isAcceptedStringBackwards

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:

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.

runForwards

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 SQ, the given label l ∈ Σ, and the returned set of states S'Q. S' = M ∪ E where:

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

E =

the empty set if this FSA does not support epsilon transitions

epsilonClosureForwards(M) otherwise

PRECONDITIONS:

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

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:

inputString 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:

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

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 ∪ E where:

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

E =

the empty set if this FSA does not support epsilon transitions

epsilonClosureBackwards(M) otherwise

PRECONDITIONS:

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

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:

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

PRECONDITIONS:

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.

supportsRunningBackwards

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

Returns:
True if running backwards is supported and false otherwise