src/main/java/de/dfki/lt/loot/fsa/algo/Determinization.java
public static <EdgeInfo> void determinize(
    AbstractAutomaton<EdgeInfo> nonDetAutomaton,
    Comparator<EdgeInfo> comp,
    AbstractAutomaton<EdgeInfo> detAutomaton) {
    // detAutomaton will contain the result DFA

    // this maps NFA state sets to a single state of the DFA
    Map<TIntHashSet, Integer> nfa2dfaStates =
      new HashMap<TIntHashSet, Integer>();

    // this contains the set of unmarked DFA states, represented by the
    // corresponding NFA state sets
    Queue<TIntHashSet> unmarkedStates
      = initUnmarkedStates(nonDetAutomaton, nfa2dfaStates, detAutomaton);

    // is there still a new DFA state we have to handle?
    while (! unmarkedStates.isEmpty()) {

      // this set of NFA states represents a single DFA state
      TIntHashSet nfaStateSet = unmarkedStates.remove();
      // this is the corresponding DFA state
      int dfaState = nfa2dfaStates.get(nfaStateSet);

      // iterate over every transition character used in this automaton
      for (EdgeInfo oneChar : nonDetAutomaton.getAlphabet()) {
        // compute the set of states that can be reached from the NFA states in
        // nfaStateSet over a transition with character oneChar
        TIntHashSet transNfaStateSet =
          move(nonDetAutomaton, nfaStateSet, oneChar, comp);

        // and do the epsilon closure of this set
        expandWithEpsilonClosure(nonDetAutomaton, transNfaStateSet);
        // if no state can be reached, we just continue
        if (transNfaStateSet.isEmpty()) {
          continue;
        }

        // this new subset of NFA states is either a known or a new state
        // of the DFA
        Integer transDfaState = nfa2dfaStates.get(transNfaStateSet);
        if (transDfaState == null) {
          // this subset represents a new DFA node, add a new node to the
          // deterministic automaton
          transDfaState = detAutomaton.newVertex();
          // add the new state to the final states if the NFA state set
          // contains a final state
          if (isFinal(nonDetAutomaton, transNfaStateSet)) {
            detAutomaton.setFinalState(transDfaState);
          }
          // created mapping from NFA state set to DFA state
          nfa2dfaStates.put(transNfaStateSet, transDfaState);
          // this node still has to be treated, so add it to the "unmarked" list
          unmarkedStates.add(transNfaStateSet);
        }
        // TODO when the edges of the original automaton carry weights, the
        // edge label used here should not come from the alphabet, but be
        // computed from the edges used in the `move' operation.
        // This is not the PROPER determinization of weighted automata, just
        // a heuristic
        // add the newly computed transition to the resulting DFA
        detAutomaton.newEdge(oneChar, dfaState, transDfaState);
      }
    }
  }
/**
   * This computes a deterministic automaton that accepts the same language as
   * this non-deterministic automaton into detAutomaton
   *
   * @param detAutomaton the resulting deterministic automaton. Must be a fresh
   *           automaton and is passed as parameter to make it possible to use
   *           this method for subclasses.
   */
This computes a deterministic automaton that accepts the same language as
this non-deterministic automaton into detAutomaton

@param detAutomaton the resulting deterministic automaton. Must be a fresh
automaton and is passed as parameter to make it possible to use
this method for subclasses.
This computes a deterministic automaton that accepts the same language as this non - deterministic automaton into detAutomaton @param detAutomaton the resulting deterministic automaton . Must be a fresh automaton and is passed as parameter to make it possible to use this method for subclasses .
public static <EdgeInfo> void determinize(
    AbstractAutomaton<EdgeInfo> nonDetAutomaton,
    Comparator<EdgeInfo> comp,
    AbstractAutomaton<EdgeInfo> detAutomaton) {
    Map<TIntHashSet, Integer> nfa2dfaStates =
      new HashMap<TIntHashSet, Integer>();
    Queue<TIntHashSet> unmarkedStates
      = initUnmarkedStates(nonDetAutomaton, nfa2dfaStates, detAutomaton);
    while (! unmarkedStates.isEmpty()) {
      TIntHashSet nfaStateSet = unmarkedStates.remove();
      int dfaState = nfa2dfaStates.get(nfaStateSet);
      for (EdgeInfo oneChar : nonDetAutomaton.getAlphabet()) {
        TIntHashSet transNfaStateSet =
          move(nonDetAutomaton, nfaStateSet, oneChar, comp);
        expandWithEpsilonClosure(nonDetAutomaton, transNfaStateSet);
        if (transNfaStateSet.isEmpty()) {
          continue;
        }
        Integer transDfaState = nfa2dfaStates.get(transNfaStateSet);
        if (transDfaState == null) {
          transDfaState = detAutomaton.newVertex();
          if (isFinal(nonDetAutomaton, transNfaStateSet)) {
            detAutomaton.setFinalState(transDfaState);
          }
          nfa2dfaStates.put(transNfaStateSet, transDfaState);
          unmarkedStates.add(transNfaStateSet);
        }
        detAutomaton.newEdge(oneChar, dfaState, transDfaState);
      }
    }
  }
public static < EdgeInfo > void determinize ( AbstractAutomaton < EdgeInfo > nonDetAutomaton , Comparator < EdgeInfo > comp , AbstractAutomaton < EdgeInfo > detAutomaton ) { Map < TIntHashSet , Integer > nfa2dfaStates = new HashMap < TIntHashSet , Integer > ( ) ; Queue < TIntHashSet > unmarkedStates = initUnmarkedStates ( nonDetAutomaton , nfa2dfaStates , detAutomaton ) ; while ( ! unmarkedStates . isEmpty ( ) ) { TIntHashSet nfaStateSet = unmarkedStates . remove ( ) ; int dfaState = nfa2dfaStates . get ( nfaStateSet ) ; for ( EdgeInfo oneChar : nonDetAutomaton . getAlphabet ( ) ) { TIntHashSet transNfaStateSet = move ( nonDetAutomaton , nfaStateSet , oneChar , comp ) ; expandWithEpsilonClosure ( nonDetAutomaton , transNfaStateSet ) ; if ( transNfaStateSet . isEmpty ( ) ) { continue ; } Integer transDfaState = nfa2dfaStates . get ( transNfaStateSet ) ; if ( transDfaState == null ) { transDfaState = detAutomaton . newVertex ( ) ; if ( isFinal ( nonDetAutomaton , transNfaStateSet ) ) { detAutomaton . setFinalState ( transDfaState ) ; } nfa2dfaStates . put ( transNfaStateSet , transDfaState ) ; unmarkedStates . add ( transNfaStateSet ) ; } detAutomaton . newEdge ( oneChar , dfaState , transDfaState ) ; } } }
This computes a deterministic automaton that accepts the same language as
 this non-deterministic automaton into detAutomaton
This computes a deterministic automaton that accepts the same language as this non - deterministic automaton into detAutomaton
// detAutomaton will contain the result DFA // this maps NFA state sets to a single state of the DFA // this contains the set of unmarked DFA states, represented by the // corresponding NFA state sets // is there still a new DFA state we have to handle? // this set of NFA states represents a single DFA state // this is the corresponding DFA state // iterate over every transition character used in this automaton // compute the set of states that can be reached from the NFA states in // nfaStateSet over a transition with character oneChar // and do the epsilon closure of this set // if no state can be reached, we just continue // this new subset of NFA states is either a known or a new state // of the DFA // this subset represents a new DFA node, add a new node to the // deterministic automaton // add the new state to the final states if the NFA state set // contains a final state // created mapping from NFA state set to DFA state // this node still has to be treated, so add it to the "unmarked" list // TODO when the edges of the original automaton carry weights, the // edge label used here should not come from the alphabet, but be // computed from the edges used in the `move' operation. // This is not the PROPER determinization of weighted automata, just // a heuristic // add the newly computed transition to the resulting DFA