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

java.lang.Object
  extended by laser.regularlanguage.fsa.util.Minimizer<L>

public class Minimizer<L extends LabelInterface>
extends java.lang.Object

Minimizes the number of states of the given DFA, including deleting dead and unreachable states. See the algorithm 3.6 in "Compilers -- Principles, Techniques, and tools" (Alfred V. Aho et el., p143, 1987) This current implementation uses an algorithm with worst case complexity of O(n^2). O(n log(n)) algorithms for this exist and can be used if it becomes necessary.

Author:
Jamieson M. Cobleigh (laser-software@cs.umass.edu), Heather M. Conboy

Constructor Summary
Minimizer()
          Creates a new Minimizer.
 
Method Summary
protected  java.lang.Object[] getCreateArgs(FSAInterface<L> newFSA, java.util.Set<? extends FSAStateInterface<L>> oldStates)
          Gets any required arguments for the state factory method from the given set of states.
protected  FSAStateInterface<L> getNextState(FSAStateInterface<L> state, L aLabel)
          Takes the given state and specified label and gets the next state.
protected  FSALabelTransitionInterface<L> getOutTransition(laser.regularlanguage.fsa.util.Minimizer.Component currentInStates, laser.regularlanguage.fsa.util.Minimizer.Component nextInStates, MutableFSAInterface<L> outDFA, FSAStateInterface<L> currentOutState, FSAStateInterface<L> nextOutState, L outLabel)
          Creates and/or gets the transition on the given label in the minimal DFA.
 RunnableFSAInterface<L> minimize(RunnableFSAInterface<L> inFsa)
          Performs DFA minimization on the inFsa, and stores the result in the outFsa.
 RunnableFSAInterface<L> minimize(RunnableFSAInterface<L> inFsa, FSAFactoryInterface<L> dfaFactory)
          Performs DFA minimization on the inFsa, and stores the result in the outFsa.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Minimizer

public Minimizer()
Creates a new Minimizer.

Method Detail

minimize

public RunnableFSAInterface<L> minimize(RunnableFSAInterface<L> inFsa)
Performs DFA minimization on the inFsa, and stores the result in the outFsa. PRECONDITIONS:

Parameters:
inFsa - the Fsa to perform minimization on
Returns:
outFsa the minimized version of inFsa

minimize

public RunnableFSAInterface<L> minimize(RunnableFSAInterface<L> inFsa,
                                        FSAFactoryInterface<L> dfaFactory)
Performs DFA minimization on the inFsa, and stores the result in the outFsa. PRECONDITIONS:

Parameters:
inFsa - the Fsa to perform minimization on
dfaFactory - The FSAFactoryInterface to be used to create the new DFA
Returns:
outFsa the minimized version of inFsa

getCreateArgs

protected java.lang.Object[] getCreateArgs(FSAInterface<L> newFSA,
                                           java.util.Set<? extends FSAStateInterface<L>> oldStates)
Gets any required arguments for the state factory method from the given set of states.

Parameters:
newFSA - The FSA that will contain the new state
oldStates - The set of old states
Returns:
Any required arguments for the new state

getNextState

protected FSAStateInterface<L> getNextState(FSAStateInterface<L> state,
                                            L aLabel)
Takes the given state and specified label and gets the next state.

Parameters:
state - The Fsa state of interest
aLabel - The label of interest
Returns:
The Fsa state that is the destination of the transition on label

getOutTransition

protected FSALabelTransitionInterface<L> getOutTransition(laser.regularlanguage.fsa.util.Minimizer.Component currentInStates,
                                                          laser.regularlanguage.fsa.util.Minimizer.Component nextInStates,
                                                          MutableFSAInterface<L> outDFA,
                                                          FSAStateInterface<L> currentOutState,
                                                          FSAStateInterface<L> nextOutState,
                                                          L outLabel)
Creates and/or gets the transition on the given label in the minimal DFA.

Parameters:
currentInStates - The current input DFA states
nextInStates - The next input DFA states
outDFA - The minimal DFA that will contain the new transition
currentOutState - The current output DFA state
nextOutState - The next output DFA state
outLabel - The label for the new transition
Returns:
The new transition on the given label