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

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

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

Converts an NFA (Nondetermanistic Finite State Automaton) to a DFA (Determanistic Finite State Automaton). This conversion can create a DFA with 2^n states where n is the number of states in the NFA. See algorithm 3.2 in "Compilers -- Principles, Techniques, and tools" (Alfred V. Aho et el., p118, 1987)

Author:
Jamieson M. Cobleigh (jcobleig@cs.umass.edu), Heather M. Conboy

Constructor Summary
NFAtoDFAConverter()
          Creates a new NFAtoDFAConverter.
 
Method Summary
 RunnableFSAInterface<L> convert(RunnableFSAInterface<L> nfa)
          Converts an NFA to a DFA.
 RunnableFSAInterface<L> convert(RunnableFSAInterface<L> nfa, FSAFactoryInterface<L> dfaFactory)
          Converts an NFA to a DFA.
protected  FSALabelTransitionInterface<L> createTransition(java.util.Set<? extends FSAStateInterface<L>> oldSources, java.util.Set<? extends FSAStateInterface<L>> oldTargets, MutableFSAInterface<L> newDFA, FSAStateInterface<L> newSource, FSAStateInterface<L> newTarget, L newLabel)
          Creates a new transition on the given label in the DFA.
protected  java.lang.Object[] getCreateArgs(MutableFSAInterface<L> newFSA, java.util.Set<? extends FSAStateInterface<L>> oldStates)
          Gets any required arguments for the state factory method from the given set of states.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

NFAtoDFAConverter

public NFAtoDFAConverter()
Creates a new NFAtoDFAConverter.

Method Detail

convert

public RunnableFSAInterface<L> convert(RunnableFSAInterface<L> nfa)
Converts an NFA to a DFA.

PRECONDITIONS:

Parameters:
nfa - The NFA to convert to a DFA (cannot be null)
Returns:
The new DFA

convert

public RunnableFSAInterface<L> convert(RunnableFSAInterface<L> nfa,
                                       FSAFactoryInterface<L> dfaFactory)
Converts an NFA to a DFA. PRECONDITIONS:

Parameters:
nfa - The NFA to convert to a DFA (cannot be null)
dfaFactory - The FSAFactoryInterface to be used to create the new DFA
Returns:
The new DFA

getCreateArgs

protected java.lang.Object[] getCreateArgs(MutableFSAInterface<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

createTransition

protected FSALabelTransitionInterface<L> createTransition(java.util.Set<? extends FSAStateInterface<L>> oldSources,
                                                          java.util.Set<? extends FSAStateInterface<L>> oldTargets,
                                                          MutableFSAInterface<L> newDFA,
                                                          FSAStateInterface<L> newSource,
                                                          FSAStateInterface<L> newTarget,
                                                          L newLabel)
Creates a new transition on the given label in the DFA.

Parameters:
oldSources - The set of old source states in the NFA
oldTargets - The set of old target states in the NFA
newDFA - The DFA that will contain the new transition
newSource - The source state in the DFA
newTarget - The target state in the DFA
newLabel - The label for the new transition
Returns:
The new transition on the given label