private IntPair complement(IntPair nfa){
  if (Options.DEBUG) {
    Out.debug("complement for " + nfa);
    Out.debug("NFA is :" + Out.NL + this);
  }
  int dfaStart=nfa.end + 1;
  epsilonFill();
  Hashtable dfaStates=new Hashtable(numStates);
  Vector dfaVector=new Vector(numStates);
  int numDFAStates=0;
  int currentDFAState=0;
  StateSet currentState, newState;
  newState=epsilon[nfa.start];
  dfaStates.put(newState,new Integer(numDFAStates));
  dfaVector.addElement(newState);
  if (Options.DEBUG)   Out.debug("pos DFA start state is :" + Out.NL + dfaStates+ Out.NL+ Out.NL+ "ordered :"+ Out.NL+ dfaVector);
  currentDFAState=0;
  while (currentDFAState <= numDFAStates) {
    currentState=(StateSet)dfaVector.elementAt(currentDFAState);
    for (char input=0; input < numInput; input++) {
      newState=DFAEdge(currentState,input);
      if (newState.containsElements()) {
        Integer nextDFAState=(Integer)dfaStates.get(newState);
        if (nextDFAState != null) {
          addTransition(dfaStart + currentDFAState,input,dfaStart + nextDFAState.intValue());
        }
 else {
          if (Options.dump)           Out.print("+");
          numDFAStates++;
          dfaStates.put(newState,new Integer(numDFAStates));
          dfaVector.addElement(newState);
          addTransition(dfaStart + currentDFAState,input,dfaStart + numDFAStates);
        }
      }
    }
    currentDFAState++;
  }
  if (Options.DEBUG)   Out.debug("dfa finished, nfa is now :" + Out.NL + this);
  int start=dfaStart + numDFAStates + 1;
  int error=dfaStart + numDFAStates + 2;
  int end=dfaStart + numDFAStates + 3;
  addEpsilonTransition(start,dfaStart);
  for (int i=0; i < numInput; i++)   addTransition(error,i,error);
  addEpsilonTransition(error,end);
  for (int s=0; s <= numDFAStates; s++) {
    currentState=(StateSet)dfaVector.elementAt(s);
    currentDFAState=dfaStart + s;
    if (!currentState.isElement(nfa.end))     addEpsilonTransition(currentDFAState,end);
    for (int i=0; i < numInput; i++)     if (table[currentDFAState][i] == null)     addTransition(currentDFAState,i,error);
  }
  if (live == null || live.length < numStates) {
    live=new boolean[2 * numStates];
    visited=new boolean[2 * numStates];
  }
  removeDead(dfaStart,end);
  if (Options.DEBUG)   Out.debug("complement finished, nfa (" + start + ","+ end+ ") is now :"+ this);
  return new IntPair(start,end);
}

private IntPair complement ( IntPair nfa ) { if ( Options . DEBUG ) { Out . debug ( "complement for " + nfa ) ; Out . debug ( "NFA is :" + Out . NL + this ) ; } int dfaStart = nfa . end + 1 ; epsilonFill ( ) ; Hashtable dfaStates = new Hashtable ( numStates ) ; Vector dfaVector = new Vector ( numStates ) ; int numDFAStates = 0 ; int currentDFAState = 0 ; StateSet currentState , newState ; newState = epsilon [ nfa . start ] ; dfaStates . put ( newState , new Integer ( numDFAStates ) ) ; dfaVector . addElement ( newState ) ; if ( Options . DEBUG ) Out . debug ( "pos DFA start state is :" + Out . NL + dfaStates + Out . NL + Out . NL + "ordered :" + Out . NL + dfaVector ) ; currentDFAState = 0 ; while ( currentDFAState <= numDFAStates ) { currentState = ( StateSet ) dfaVector . elementAt ( currentDFAState ) ; for ( char input = 0 ; input < numInput ; input ++ ) { newState = DFAEdge ( currentState , input ) ; if ( newState . containsElements ( ) ) { Integer nextDFAState = ( Integer ) dfaStates . get ( newState ) ; if ( nextDFAState != null ) { addTransition ( dfaStart + currentDFAState , input , dfaStart + nextDFAState . intValue ( ) ) ; } else { if ( Options . dump ) Out . print ( "+" ) ; numDFAStates ++ ; dfaStates . put ( newState , new Integer ( numDFAStates ) ) ; dfaVector . addElement ( newState ) ; addTransition ( dfaStart + currentDFAState , input , dfaStart + numDFAStates ) ; } } } currentDFAState ++ ; } if ( Options . DEBUG ) Out . debug ( "dfa finished, nfa is now :" + Out . NL + this ) ; int start = dfaStart + numDFAStates + 1 ; int error = dfaStart + numDFAStates + 2 ; int end = dfaStart + numDFAStates + 3 ; addEpsilonTransition ( start , dfaStart ) ; for ( int i = 0 ; i < numInput ; i ++ ) addTransition ( error , i , error ) ; addEpsilonTransition ( error , end ) ; for ( int s = 0 ; s <= numDFAStates ; s ++ ) { currentState = ( StateSet ) dfaVector . elementAt ( s ) ; currentDFAState = dfaStart + s ; if ( ! currentState . isElement ( nfa . end ) ) addEpsilonTransition ( currentDFAState , end ) ; for ( int i = 0 ; i < numInput ; i ++ ) if ( table [ currentDFAState ] [ i ] == null ) addTransition ( currentDFAState , i , error ) ; } if ( live == null || live . length < numStates ) { live = new boolean [ 2 * numStates ] ; visited = new boolean [ 2 * numStates ] ; } removeDead ( dfaStart , end ) ; if ( Options . DEBUG ) Out . debug ( "complement finished, nfa (" + start + "," + end + ") is now :" + this ) ; return new IntPair ( start , end ) ; }
constructs an nfa accepting the complement of the language of a given nfa . converts the nfa into a dfa , then negates that dfa . exponential state blowup possible and common .
