laser.regularlanguage.fsa.util
Class AbstractFSAs<L extends LabelInterface>

java.lang.Object
  extended by laser.regularlanguage.fsa.util.AbstractFSAs<L>
Type Parameters:
L - The type of labels used by the FSAs
Direct Known Subclasses:
FSAs

public abstract class AbstractFSAs<L extends LabelInterface>
extends java.lang.Object

The AbstractFSAs class contains various methods for manipulating finite state automata (FSAs) such as regular operations, set operations, and others.

Define the alphabet of FSA M to be Σ(M) the set of all labels used by FSA M.

Define the language of FSA M to be L(M) the set of all input strings accepted by FSA M.

The methods in this class all throw an IllegalArgumentException if the given FSA is null or is not well-formed.

Author:
Heather M. Conboy (laser-software@cs.umass.edu)
See Also:
AlphabetInterface, LabelInterface, FSAInterface, MutableFSAInterface, RunnableFSAInterface

Constructor Summary
AbstractFSAs()
           
 
Method Summary
abstract  MutableFSAInterface<L> complement(RunnableFSAInterface<L> fsa)
          Returns an FSA that is the complement of the given FSA.
abstract  MutableFSAInterface<L> concatenation(FSAInterface<L> fsa1, FSAInterface<L> fsa2)
          Returns an FSA that is the concatenation of the given FSAs.
abstract  RunnableFSAInterface<L> convertFSAtoDFA(RunnableFSAInterface<L> fsa)
          Converts from the given FSA into the corresponding DFA.
abstract  MutableFSAInterface<L> convertFSAtoNFA(FSAInterface<L> fsa)
          Converts from the given FSA into the corresponding NFA.
abstract  boolean deleteUnnecessaryStates(MutableFSAInterface<L> fsa)
          Deletes any unnecessary states from the given FSA.
abstract  RunnableFSAInterface<L> determinize(RunnableFSAInterface<L> fsa)
          Returns a determinisitic FSA that corresponds to the given FSA.
abstract  RunnableFSAInterface<L> differenceAsymmetric(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the asymmetric difference of the first FSA and the second FSA.
abstract  RunnableFSAInterface<L> differenceSymmetric(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the symmetric difference of the given FSAs.
abstract  MutableFSAInterface<L> empty(AlphabetInterface<L> alphabet, java.lang.Object[] stateArgs, java.lang.Object[] transitionArgs, java.lang.Object... fsaArgs)
          Returns an FSA that accepts no input strings.
abstract  MutableFSAInterface<L> epsilon(AlphabetInterface<L> alphabet, java.lang.Object[] stateArgs, java.lang.Object[] transitionArgs, java.lang.Object... fsaArgs)
          Returns an FSA that accepts the empty string.
abstract  FSAFactoryInterface<L> getDFAFactory()
          Gets the FSAFactoryInterface to be used to create new DFAs.
abstract  FSAFactoryInterface<L> getFSAFactory()
          Gets the FSAFactoryInterface to be used to create new FSAs.
abstract  MutableFSAInterface<L> inflateConstructive(FSAInterface<L> fsa, AlphabetInterface<L> newAlphabet, java.lang.Object... transitionArgs)
          Inflates the given FSA with regards to the specified Alphabet.
abstract  void inflateDestructive(MutableFSAInterface<L> fsa, AlphabetInterface<L> newAlphabet, java.lang.Object... transitionArgs)
          Inflates the given FSA with regards to the specified Alphabet.
abstract  RunnableFSAInterface<L> intersect(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the intersection of the given FSAs.
abstract  boolean isEmpty(RunnableFSAInterface<L> fsa)
          Returns true if the given FSA accepts no input strings (including the empty string), false otherwise.
abstract  boolean isEquivalent(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns true if the first FSA accepts the same set of input strings as the second FSA, false otherwise.
abstract  MutableFSAInterface<L> label(L label, AlphabetInterface<L> alphabet, java.lang.Object[] stateArgs, java.lang.Object[] transitionArgs, java.lang.Object... fsaArgs)
          Returns an FSA that accepts the specified label.
abstract  RunnableFSAInterface<L> minimize(RunnableFSAInterface<L> fsa)
          Returns the minimal deterministic FSA that corresponds to the given FSA.
abstract  RunnableFSAInterface<L> product(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the product of the given FSAs.
abstract  void replaceLabelsWithEpsilon(MutableFSAInterface<L> fsa, java.util.Set<? extends L> labels, java.lang.Object... epsilonTransitionArgs)
          Removes the given Labels from the specified FSA and when a Label is removed from the Alphabet of the FSA with this method, all transitions on that Label are likewise removed, and epsilon (ε) transitions with the same source and target states are added.
abstract  MutableFSAInterface<L> reverse(FSAInterface<L> fsa)
          Reverses the given FSA.
abstract  MutableFSAInterface<L> star(FSAInterface<L> fsa)
          Returns an FSA that is the star of the given FSA.
abstract  RunnableFSAInterface<L> union(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the union of the given FSAs.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AbstractFSAs

public AbstractFSAs()
Method Detail

getFSAFactory

public abstract FSAFactoryInterface<L> getFSAFactory()
Gets the FSAFactoryInterface to be used to create new FSAs.

Returns:
The FSAFactoryInterface to be used to create new FSAs

getDFAFactory

public abstract FSAFactoryInterface<L> getDFAFactory()
Gets the FSAFactoryInterface to be used to create new DFAs.

Returns:
The FSAFactoryInterface to be used to create new DFAs

isEmpty

public abstract boolean isEmpty(RunnableFSAInterface<L> fsa)
Returns true if the given FSA accepts no input strings (including the empty string), false otherwise.

PRECONDITION: The FSA must be non-null.

Returns:
true if the given FSA accepts no input strings (including the empty string), false otherwise.

isEquivalent

public abstract boolean isEquivalent(RunnableFSAInterface<L> fsa1,
                                     RunnableFSAInterface<L> fsa2)
Returns true if the first FSA accepts the same set of input strings as the second FSA, false otherwise.

PRECONDITION: The first and second FSA must be non-null.

Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
true if the first FSA accepts the same set of input strings as the second FSA, false otherwise.
Throws:
java.lang.IllegalArgumentException - if the first or second FSA is null.

empty

public abstract MutableFSAInterface<L> empty(AlphabetInterface<L> alphabet,
                                             java.lang.Object[] stateArgs,
                                             java.lang.Object[] transitionArgs,
                                             java.lang.Object... fsaArgs)
Returns an FSA that accepts no input strings.

NOTE: This is a regular and set operation. The FSA factory will be used to create the new FSA.

PRECONDITIONS:

Parameters:
alphabet - The alphabet for the new FSA
stateArgs - Any required arguments for the state factory method
transitionArgs - Any required arguments for the transition factory method
fsaArgs - Any required arguments for the FSA factory method (optional)
Returns:
An FSA that accepts no input strings

epsilon

public abstract MutableFSAInterface<L> epsilon(AlphabetInterface<L> alphabet,
                                               java.lang.Object[] stateArgs,
                                               java.lang.Object[] transitionArgs,
                                               java.lang.Object... fsaArgs)
Returns an FSA that accepts the empty string.

NOTE: This is a regular and set operation. The FSA factory will be used to create the new FSA.

PRECONDITIONS:

Parameters:
alphabet - The alphabet for the new FSA
stateArgs - Any required arguments for the state factory method
transitionArgs - Any required arguments for the transition factory method
fsaArgs - Any required arguments for the FSA factory method (optional)
Returns:
An FSA that accepts the empty string

label

public abstract MutableFSAInterface<L> label(L label,
                                             AlphabetInterface<L> alphabet,
                                             java.lang.Object[] stateArgs,
                                             java.lang.Object[] transitionArgs,
                                             java.lang.Object... fsaArgs)
Returns an FSA that accepts the specified label.

NOTE: This is a regular operation.

PRECONDITIONS:

Parameters:
label - The specified label
alphabet - The alphabet for the new FSA
stateArgs - Any required arguments for the state factory method
transitionArgs - Any required arguments for the transition factory method
fsaArgs - Any required arguments for the FSA factory method (optional)
Returns:
An FSA that accepts the specified label

concatenation

public abstract MutableFSAInterface<L> concatenation(FSAInterface<L> fsa1,
                                                     FSAInterface<L> fsa2)
Returns an FSA that is the concatenation of the given FSAs. Call the returned FSA concatFSA. Formally, Σ(concatFSA) is Σ(fsa1) ∪ Σ(fsa2) and L(concatFSA) is L(fsa1) ⋅ L(fsa2).

L(concatFSA) = { x ⋅ y | x ∈ L(fsa1) and y ∈ L(fsa2) }

NOTE: This is a regular operation.

PRECONDITIONS:

Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the concatenation of the given FSAs.

star

public abstract MutableFSAInterface<L> star(FSAInterface<L> fsa)
Returns an FSA that is the star of the given FSA. Call the returned FSA starFSA. Formally, Σ(starFSA) is Σ(fsa) and L(starFSA) is L(fsa)*.

L(starFSA) = {x_1, x_2, ..., x_k | k >= 0 and each x_i ∈ L(fsa) }

NOTE: This is a regular operation.

PRECONDITIONS:

Parameters:
fsa - The FSA.
Returns:
An FSA that is the star of the given FSA.

union

public abstract RunnableFSAInterface<L> union(RunnableFSAInterface<L> fsa1,
                                              RunnableFSAInterface<L> fsa2)
Returns an FSA that is the union of the given FSAs. Call the returned FSA unionFSA. Formally, Σ(unionFSA) is Σ(fsa1) ∪ Σ(fsa2) and L(unionFSA) is L(fsa1) ∪ L(fsa2).

L(unionFSA) = { x | x ∈ L(fsa1) or x ∈ L(fsa2) }

If the original FSAs have no epsilon transitions, the resulting FSA will have no epsilon transitions. If the original FSAs are deterministic, the resulting FSA will be deterministic.

NOTE: This is a regular operation.

PRECONDITIONS: The first and second FSA must be non-null.

Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the union of the given FSAs.

complement

public abstract MutableFSAInterface<L> complement(RunnableFSAInterface<L> fsa)
Returns an FSA that is the complement of the given FSA. Call the returned FSA compFSA. Formally, Σ(compFSA) is Σ(fsa) and L(compFSA) = { x | x ∉ L(fsa) }.

NOTE: This is a set operation.

PRECONDITION: The FSA must be non-null.

Parameters:
fsa - The given FSA.
Returns:
An FSA that is the complement of the given FSA.

differenceAsymmetric

public abstract RunnableFSAInterface<L> differenceAsymmetric(RunnableFSAInterface<L> fsa1,
                                                             RunnableFSAInterface<L> fsa2)
Returns an FSA that is the asymmetric difference of the first FSA and the second FSA. Call the returned FSA diffFSA. Formally, Σ(diffFSA) is Σ(fsa1) ∪ L(fsa2) and L(diffFSA) is L(fsa1) ∖ L(fsa2).

L(diffFSA) = { x | x ∈ L(fsa1) and x ∉ L(fsa2) }

NOTE: This is a set operation.

PRECONDITIONS: The first and second FSA must be non-null.

Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the asymmetric difference of the given FSAs.

differenceSymmetric

public abstract RunnableFSAInterface<L> differenceSymmetric(RunnableFSAInterface<L> fsa1,
                                                            RunnableFSAInterface<L> fsa2)
Returns an FSA that is the symmetric difference of the given FSAs. Call the returned FSA diffFSA. Formally, Σ(diffFSA) is Σ(fsa1) ∪ L(fsa2) and L(diffFSA) is L(fsa1) ⊕ L(fsa2).

L(diffFSA) = { x | x ∈ (L(fsa1) and x ∉ L(fsa2)) or (x ∉ L(fsa1) and x ∈ L(fsa2)) }

NOTE: This is a set operation.

PRECONDITIONS: The first and second FSA must be non-null.

Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the symmetric difference of the given FSAs.

intersect

public abstract RunnableFSAInterface<L> intersect(RunnableFSAInterface<L> fsa1,
                                                  RunnableFSAInterface<L> fsa2)
Returns an FSA that is the intersection of the given FSAs. Call the returned FSA intersectFSA. Formally, Σ(intersectFSA) is Σ(fsa1) ∪ Σ(fsa2) and L(intersectFSA) is L(fsa1) ⋂ L(fsa2).

L(intersectFSA) = { x | x ∈ L(fsa1) and x ∈ L(fsa2) }

NOTE: This is a set operation.

PRECONDITIONS: The first and second FSA must be non-null.

Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the intersection of the given FSAs.

product

public abstract RunnableFSAInterface<L> product(RunnableFSAInterface<L> fsa1,
                                                RunnableFSAInterface<L> fsa2)
Returns an FSA that is the product of the given FSAs. Call the the returned FSA productFSA. Σ(productFSA) is Σ(fsa1) ∪ Σ(fsa2) and L(productFSA) is L(fsa1) X L(fsa2).

L(productFSA) = {s = l1, l2, …, ln : (∀ 1 ≤ in : li ∈ Σ1 ∪ Σ2) ∧ s |Σ1L(fsa1) ∧ s |Σ2L(fsa2)}.

If the original FSAs have no epsilon transitions, the resulting FSA will have no epsilon transitions. If the original FSAs are deterministic, the resulting FSA will be deterministic.

NOTE: This is a set operation.

PRECONDITIONS: The first and second FSA must be non-null.

Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the product of the given FSAs.

convertFSAtoDFA

public abstract RunnableFSAInterface<L> convertFSAtoDFA(RunnableFSAInterface<L> fsa)
Converts from the given FSA into the corresponding DFA.

NOTE: The DFA factory will be used to create the new DFA.

PRECONDITIONS:

Parameters:
fsa - The FSA to be converted
Returns:
The corresponding DFA
See Also:
getDFAFactory(), determinize(laser.regularlanguage.fsa.RunnableFSAInterface)

convertFSAtoNFA

public abstract MutableFSAInterface<L> convertFSAtoNFA(FSAInterface<L> fsa)
Converts from the given FSA into the corresponding NFA.

NOTE: The FSA factory will be used to create the new NFA.

PRECONDITIONS:

Parameters:
fsa - The FSA to be converted
Returns:
The corresponding NFA
See Also:
getFSAFactory()

deleteUnnecessaryStates

public abstract boolean deleteUnnecessaryStates(MutableFSAInterface<L> fsa)
Deletes any unnecessary states from the given FSA. An unnecessary state is dead and/or unreachable.

PRECONDITIONS:

Parameters:
fsa - The FSA to be considered
Returns:
True if any unnecessary states were removed and false otherwise
See Also:
MutableFSAInterface.deleteDeadStates(), MutableFSAInterface.deleteUnreachableStates()

determinize

public abstract RunnableFSAInterface<L> determinize(RunnableFSAInterface<L> fsa)
Returns a determinisitic FSA that corresponds to the given FSA. Call the returned FSA dfa. Σ(dfa) is Σ(fsa) and L(dfa) is L(fsa).

PRECONDITION: The FSA must be non-null.

POSTCONDITION: The returned FSA will be deterministic.

Parameters:
fsa - The given FSA.
Returns:
An FSA that accepts the exact same set of input strings as the given FSA but is deterministic.
See Also:
FSAInterface.isDeterministic()

inflateConstructive

public abstract MutableFSAInterface<L> inflateConstructive(FSAInterface<L> fsa,
                                                           AlphabetInterface<L> newAlphabet,
                                                           java.lang.Object... transitionArgs)
Inflates the given FSA with regards to the specified Alphabet. This creates a clone of the FSA, sets its alphabet to the specified Alphabet, and adds self-loop transitions (transitions for which source and target return the same state) on every state for each Label in the specified Alphabet that is not equal to a Label in the Alphabet of the given FSA.

PRECONDITIONS:

Parameters:
fsa - The given FSA.
newAlphabet - The given Alphabet.
transitionArgs - Any required arguments for the new transitions. (optional)
Returns:
The inflated FSA.

inflateDestructive

public abstract void inflateDestructive(MutableFSAInterface<L> fsa,
                                        AlphabetInterface<L> newAlphabet,
                                        java.lang.Object... transitionArgs)
Inflates the given FSA with regards to the specified Alphabet. This sets its alphabet to the specified Alphabet and adds self-loop transitions (transitions for which source and target return the same state) on every state for each Label in the specified Alphabet that is not equal to a Label in the Alphabet of the given FSA.

PRECONDITIONS:

Parameters:
fsa - The given FSA.
newAlphabet - The given Alphabet.
transitionArgs - Any required arguments for the new transitions. (optional)

minimize

public abstract RunnableFSAInterface<L> minimize(RunnableFSAInterface<L> fsa)
Returns the minimal deterministic FSA that corresponds to the given FSA. Call the returned FSA dfa. Σ(dfa) is Σ(fsa) and Q(dfa) has the minimal number of states and L(dfa) is L(fsa).

PRECONDITION: The FSA must be non-null.

POSTCONDITION: The returned FSA will be deterministic and minimal.

Parameters:
fsa - The given FSA.
Returns:
The minimal deterministic FSA that accepts the exact same set of input strings as the given FSA but has a minimal number of states.
See Also:
FSAInterface.isDeterministic()

replaceLabelsWithEpsilon

public abstract void replaceLabelsWithEpsilon(MutableFSAInterface<L> fsa,
                                              java.util.Set<? extends L> labels,
                                              java.lang.Object... epsilonTransitionArgs)
Removes the given Labels from the specified FSA and when a Label is removed from the Alphabet of the FSA with this method, all transitions on that Label are likewise removed, and epsilon (ε) transitions with the same source and target states are added.

PRECONDITIONS:

POSTCONDITIONS:

Parameters:
fsa - The given FSA to be processed.
labels - The Set containing Labels to be replaced.
epsilonTransitionArgs - Any required arguments for the epsilon transition factory method. (optional)
Throws:
java.lang.IllegalArgumentException - the specified fsa or the Set of labels or any of its elements is null.
java.lang.UnsupportedOperationException - The given FSA does not support epsilon (ε) transitions.
See Also:
MutableFSAInterface.removeLabels(java.util.Set), MutableFSAInterface.removeTransition(laser.regularlanguage.fsa.FSATransitionInterface), MutableFSAInterface.addEpsilonTransition(laser.regularlanguage.fsa.FSAStateInterface, laser.regularlanguage.fsa.FSAStateInterface, java.lang.Object...)

reverse

public abstract MutableFSAInterface<L> reverse(FSAInterface<L> fsa)
Reverses the given FSA.

PRECONDITIONS:

Parameters:
fsa - The given FSA.
Returns:
The given FSA in reverse