question: 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 ) ; }
target:  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.