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

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

public class FSAs<L extends LabelInterface>
extends AbstractFSAs<L>

The FSAs 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:
FSAInterface

Field Summary
static java.lang.String DESCRIPTION_PREFIX
          The description prefix
static java.lang.String DESCRIPTION_SEPARATOR
          The description separator
static java.lang.String DESCRIPTION_SUFFIX
          The description suffix
protected  FSAFactoryInterface<L> dfaFactory_
          The FSAFactoryInterface to be used to create new DFAs
protected  FSAFactoryInterface<L> fsaFactory_
          The FSAFactoryInterface to be used to create new FSAs
static java.lang.String NAME_SEPARATOR
          The name separator
 
Constructor Summary
FSAs(FSAFactoryInterface<L> fsaFactory)
          Creates a new FSAs class.
FSAs(FSAFactoryInterface<L> fsaFactory, FSAFactoryInterface<L> dfaFactory)
          Creates a new FSAs class.
 
Method Summary
protected  void checkClass(FSAInterface<L> theFSA)
          Checks that the FSA's class is supported.
protected  void checkPreconditions(FSAInterface<L> fsa)
          Checks the preconditions for the given FSA.
 MutableFSAInterface<L> complement(RunnableFSAInterface<L> fsa)
          Returns an FSA that is the complement of the given FSA.
 MutableFSAInterface<L> concatenation(FSAInterface<L> fsa1, FSAInterface<L> fsa2)
          Returns an FSA that is the concatenation of the given FSAs.
 RunnableFSAInterface<L> convertFSAtoDFA(RunnableFSAInterface<L> fsa)
          Converts from the given FSA into the corresponding DFA.
 MutableFSAInterface<L> convertFSAtoNFA(FSAInterface<L> fsa)
          Converts from the given FSA into the corresponding NFA.
protected  NFAtoDFAConverter<L> createDeterminizer()
          Creates a new Determinimzer.
protected  Inflater<L> createInflater()
          Creates a new Inflater.
protected  IntersectionComposer<L> createIntersectComposer()
          Creates a new IntersectionComposer.
protected  Minimizer<L> createMinimizer()
          Creates a new Minimizer.
protected  ProductComposer<L> createProductComposer()
          Creates a new ProductComposer.
protected  UnionComposer<L> createUnionComposer()
          Creates a new UnionComposer.
 boolean deleteUnnecessaryStates(MutableFSAInterface<L> fsa)
          Deletes any unnecessary states from the given FSA.
 RunnableFSAInterface<L> determinize(RunnableFSAInterface<L> fsa)
          Returns a determinisitic FSA that corresponds to the given FSA.
 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.
 RunnableFSAInterface<L> differenceSymmetric(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the symmetric difference of the given FSAs.
 MutableFSAInterface<L> empty(AlphabetInterface<L> alphabet, java.lang.Object[] stateArgs, java.lang.Object[] transitionArgs, java.lang.Object... fsaArgs)
          Returns the FSA that accepts no input strings.
 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.
 FSAFactoryInterface<L> getDFAFactory()
          Gets the FSAFactoryInterface to be used to create new DFAs.
 FSAFactoryInterface<L> getFSAFactory()
          Gets the FSAFactoryInterface to be used to create new FSAs.
 MutableFSAInterface<L> inflateConstructive(FSAInterface<L> fsa, AlphabetInterface<L> newAlphabet, java.lang.Object... transitionArgs)
          Inflates the given FSA with regards to the specified Alphabet.
 void inflateDestructive(MutableFSAInterface<L> fsa, AlphabetInterface<L> newAlphabet, java.lang.Object... transitionArgs)
          Inflates the given FSA with regards to the specified Alphabet.
 RunnableFSAInterface<L> intersect(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the intersection of the given FSAs.
 boolean isEmpty(RunnableFSAInterface<L> fsa)
          Returns true if this FSA accepts no input strings (including the empty string), false otherwise.
 boolean isEquivalent(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns true if the specified FSA accepts the same set of input strings as this FSA, false otherwise.
 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.
 RunnableFSAInterface<L> minimize(RunnableFSAInterface<L> fsa)
          Returns the minimal deterministic FSA that corresponds to the given FSA.
protected  FSAPair<L> normalize(FSAInterface<L> fsa1, FSAInterface<L> fsa2)
          Normalizes the given FSAs before a binary operation occurs.
 RunnableFSAInterface<L> product(RunnableFSAInterface<L> fsa1, RunnableFSAInterface<L> fsa2)
          Returns an FSA that is the product of the given FSAs.
 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.
 MutableFSAInterface<L> reverse(FSAInterface<L> fsa)
          Reverses the given FSA.
protected  void setFSAAttributes(FSAInterface<L> oldFSA1, FSAInterface<L> oldFSA2, FSAInterface<L> newFSA, java.lang.String binaryOp)
          Sets the attributes of the new FSA based on the attributes of the old FSAs and the given binary operation.
protected  void setFSAAttributes(FSAInterface<L> oldFSA, FSAInterface<L> newFSA, java.lang.String unaryOp)
          Sets the attributes of the new FSA based on the attributes of the old FSA and the given unary operation.
 MutableFSAInterface<L> star(FSAInterface<L> fsa)
          Returns an FSA that is the star of the given FSA.
 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
 

Field Detail

NAME_SEPARATOR

public static final java.lang.String NAME_SEPARATOR
The name separator

See Also:
Constant Field Values

DESCRIPTION_PREFIX

public static final java.lang.String DESCRIPTION_PREFIX
The description prefix

See Also:
Constant Field Values

DESCRIPTION_SEPARATOR

public static final java.lang.String DESCRIPTION_SEPARATOR
The description separator

See Also:
Constant Field Values

DESCRIPTION_SUFFIX

public static final java.lang.String DESCRIPTION_SUFFIX
The description suffix

See Also:
Constant Field Values

fsaFactory_

protected final FSAFactoryInterface<L extends LabelInterface> fsaFactory_
The FSAFactoryInterface to be used to create new FSAs


dfaFactory_

protected final FSAFactoryInterface<L extends LabelInterface> dfaFactory_
The FSAFactoryInterface to be used to create new DFAs

Constructor Detail

FSAs

public FSAs(FSAFactoryInterface<L> fsaFactory)
Creates a new FSAs class.

Parameters:
fsaFactory - The FSAFactoryInterface to be used to create new FSAs and DFAs

FSAs

public FSAs(FSAFactoryInterface<L> fsaFactory,
            FSAFactoryInterface<L> dfaFactory)
Creates a new FSAs class.

Parameters:
fsaFactory - The FSAFactoryInterface to be used to create new FSAs
dfaFactory - The FSAFactoryInterface to be used to create new DFAs
Method Detail

checkClass

protected void checkClass(FSAInterface<L> theFSA)
Checks that the FSA's class is supported.

Parameters:
theFSA - The FSA to be checked

checkPreconditions

protected void checkPreconditions(FSAInterface<L> fsa)
Checks the preconditions for the given FSA.

PRECONDITIONS:

Parameters:
fsa - The FSA to be checked

createIntersectComposer

protected IntersectionComposer<L> createIntersectComposer()
Creates a new IntersectionComposer.

Returns:
The appropriate IntersectionComposer

createProductComposer

protected ProductComposer<L> createProductComposer()
Creates a new ProductComposer.

Returns:
The appropriate ProductComposer

createUnionComposer

protected UnionComposer<L> createUnionComposer()
Creates a new UnionComposer.

Returns:
The appropriate UnionComposer

createDeterminizer

protected NFAtoDFAConverter<L> createDeterminizer()
Creates a new Determinimzer.

Returns:
The appropriate Determinizer

createInflater

protected Inflater<L> createInflater()
Creates a new Inflater.

Returns:
The appropriate Inflater

createMinimizer

protected Minimizer<L> createMinimizer()
Creates a new Minimizer.

Returns:
The appropriate Minimizer

getFSAFactory

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

Specified by:
getFSAFactory in class AbstractFSAs<L extends LabelInterface>
Returns:
The FSAFactoryInterface to be used to create new FSAs

getDFAFactory

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

Specified by:
getDFAFactory in class AbstractFSAs<L extends LabelInterface>
Returns:
The FSAFactoryInterface to be used to create new DFAs

normalize

protected FSAPair<L> normalize(FSAInterface<L> fsa1,
                               FSAInterface<L> fsa2)
Normalizes the given FSAs before a binary operation occurs.

Parameters:
fsa1 - The first FSA
fsa2 - The second FSA
Returns:
The normalized FSAs

setFSAAttributes

protected void setFSAAttributes(FSAInterface<L> oldFSA,
                                FSAInterface<L> newFSA,
                                java.lang.String unaryOp)
Sets the attributes of the new FSA based on the attributes of the old FSA and the given unary operation.

Parameters:
oldFSA - The old FSA
newFSA - The new FSA
unaryOp - The unary operation

setFSAAttributes

protected void setFSAAttributes(FSAInterface<L> oldFSA1,
                                FSAInterface<L> oldFSA2,
                                FSAInterface<L> newFSA,
                                java.lang.String binaryOp)
Sets the attributes of the new FSA based on the attributes of the old FSAs and the given binary operation.

Parameters:
oldFSA1 - The first old FSA
oldFSA2 - The second old FSA
newFSA - The new FSA
binaryOp - The binary operation

isEmpty

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

PRECONDITION: The fsa must be non-null.

Specified by:
isEmpty in class AbstractFSAs<L extends LabelInterface>
Returns:
true if this FSA accepts no input strings (including the empty string), false otherwise.

isEquivalent

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

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

Specified by:
isEquivalent in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
true if the specified FSA accepts the same set of input strings as this FSA, false otherwise.
Throws:
java.lang.IllegalArgumentException - if the first or second FSA is null.

concatenation

public 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) }

If the original FSAs have no epsilon transitions, the resulting FSA will have no epsilon transitions. Even if the original FSAs are deterministic, the resulting FSA may be non-deterministic.

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

PRECONDITIONS:

Specified by:
concatenation in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the concatenation of the given FSAs.
See Also:
getFSAFactory()

epsilon

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

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

PRECONDITIONS:

Specified by:
epsilon in class AbstractFSAs<L extends LabelInterface>
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
See Also:
getFSAFactory()

label

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

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

PRECONDITIONS:

Specified by:
label in class AbstractFSAs<L extends LabelInterface>
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
See Also:
getFSAFactory()

star

public 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) }

If the original FSA has no epsilon transitions, the resulting FSA will have no epsilon transitions. Even if the original FSA is deterministic, the resulting FSA may be non-deterministic.

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

PRECONDITIONS:

Specified by:
star in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa - The FSA.
Returns:
An FSA that is the star of the given FSA.
See Also:
getFSAFactory()

union

public 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 and set operation. The FSA factory will be used to create the new FSA.

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

Specified by:
union in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the union of the given FSAs.
See Also:
getFSAFactory()

complement

public 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. The DFA factory will be used to create the new DFA.

PRECONDITION: The FSA must be non-null.

Specified by:
complement in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa - The given FSA.
Returns:
An FSA that is the complement of the given FSA.
See Also:
getDFAFactory()

differenceAsymmetric

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

Specified by:
differenceAsymmetric in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the asymmetric difference of the given FSAs.

differenceSymmetric

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

Specified by:
differenceSymmetric in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the symmetric difference of the given FSAs.

empty

public MutableFSAInterface<L> empty(AlphabetInterface<L> alphabet,
                                    java.lang.Object[] stateArgs,
                                    java.lang.Object[] transitionArgs,
                                    java.lang.Object... fsaArgs)
Returns the 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:

Specified by:
empty in class AbstractFSAs<L extends LabelInterface>
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
See Also:
getFSAFactory()

intersect

public 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) }

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.

Specified by:
intersect in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the intersection of the given FSAs.

product

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

Specified by:
product in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa1 - The first FSA.
fsa2 - The second FSA.
Returns:
An FSA that is the product of the given FSAs.

convertFSAtoDFA

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

Specified by:
convertFSAtoDFA in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa - The FSA to be converted
Returns:
The corresponding DFA
See Also:
getDFAFactory(), determinize(laser.regularlanguage.fsa.RunnableFSAInterface)

convertFSAtoNFA

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

Specified by:
convertFSAtoNFA in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa - The FSA to be converted
Returns:
The corresponding NFA
See Also:
getFSAFactory()

deleteUnnecessaryStates

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

PRECONDITIONS:

Specified by:
deleteUnnecessaryStates in class AbstractFSAs<L extends LabelInterface>
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 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).

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

PRECONDITION: The FSA must be non-null.

POSTCONDITION: The returned FSA will be deterministic.

Specified by:
determinize in class AbstractFSAs<L extends LabelInterface>
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:
getDFAFactory(), FSAInterface.isDeterministic()

inflateConstructive

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

Specified by:
inflateConstructive in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa - The given FSA.
newAlphabet - The given Alphabet.
transitionArgs - Any required arguments for the new transitions. (optional)
Returns:
The inflated FSA.

inflateDestructive

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

Specified by:
inflateDestructive in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa - The given FSA.
newAlphabet - The given Alphabet.
transitionArgs - Any required arguments for the new transitions. (optional)

minimize

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

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

PRECONDITION: The FSA must be non-null.

POSTCONDITION: The returned FSA will be deterministic and minimal.

Specified by:
minimize in class AbstractFSAs<L extends LabelInterface>
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:
getDFAFactory(), FSAInterface.isDeterministic()

replaceLabelsWithEpsilon

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

Specified by:
replaceLabelsWithEpsilon in class AbstractFSAs<L extends LabelInterface>
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 MutableFSAInterface<L> reverse(FSAInterface<L> fsa)
Reverses the given FSA.

NOTES:

The FSA factory will be used to create the new FSA.

If the original FSA has no epsilon transitions, the resulting FSA will have no epsilon transitions. Even if the original FSA is deterministic, the resulting FSA may be non-deterministic.

PRECONDITIONS:

Specified by:
reverse in class AbstractFSAs<L extends LabelInterface>
Parameters:
fsa - The given FSA.
Returns:
The given FSA in reverse
See Also:
getFSAFactory()