question: public static Automaton determinize ( Automaton a , int maxDeterminizedStates ) { if ( a . isDeterministic ( ) ) { return a ; } if ( a . getNumStates ( ) <= 1 ) { return a ; } Automaton . Builder b = new Automaton . Builder ( ) ; SortedIntSet . FrozenIntSet initialset = new SortedIntSet . FrozenIntSet ( 0 , 0 ) ; b . createState ( ) ; LinkedList < SortedIntSet . FrozenIntSet > worklist = new LinkedList < > ( ) ; Map < SortedIntSet . FrozenIntSet , Integer > newstate = new HashMap < > ( ) ; worklist . add ( initialset ) ; b . setAccept ( 0 , a . isAccept ( 0 ) ) ; newstate . put ( initialset , 0 ) ; final PointTransitionSet points = new PointTransitionSet ( ) ; final SortedIntSet statesSet = new SortedIntSet ( 5 ) ; Transition t = new Transition ( ) ; while ( worklist . size ( ) > 0 ) { SortedIntSet . FrozenIntSet s = worklist . removeFirst ( ) ; for ( int i = 0 ; i < s . values . length ; i ++ ) { final int s0 = s . values [ i ] ; int numTransitions = a . getNumTransitions ( s0 ) ; a . initTransition ( s0 , t ) ; for ( int j = 0 ; j < numTransitions ; j ++ ) { a . getNextTransition ( t ) ; points . add ( t ) ; } } if ( points . count == 0 ) { continue ; } points . sort ( ) ; int lastPoint = - 1 ; int accCount = 0 ; final int r = s . state ; for ( int i = 0 ; i < points . count ; i ++ ) { final int point = points . points [ i ] . point ; if ( statesSet . upto > 0 ) { assert lastPoint != - 1 ; statesSet . computeHash ( ) ; Integer q = newstate . get ( statesSet ) ; if ( q == null ) { q = b . createState ( ) ; if ( q >= maxDeterminizedStates ) { throw new TooComplexToDeterminizeException ( a , maxDeterminizedStates ) ; } final SortedIntSet . FrozenIntSet p = statesSet . freeze ( q ) ; worklist . add ( p ) ; b . setAccept ( q , accCount > 0 ) ; newstate . put ( p , q ) ; } else { assert ( accCount > 0 ? true : false ) == b . isAccept ( q ) : "accCount=" + accCount + " vs existing accept=" + b . isAccept ( q ) + " states=" + statesSet ; } b . addTransition ( r , q , lastPoint , point - 1 ) ; } int [ ] transitions = points . points [ i ] . ends . transitions ; int limit = points . points [ i ] . ends . next ; for ( int j = 0 ; j < limit ; j += 3 ) { int dest = transitions [ j ] ; statesSet . decr ( dest ) ; accCount -= a . isAccept ( dest ) ? 1 : 0 ; } points . points [ i ] . ends . next = 0 ; transitions = points . points [ i ] . starts . transitions ; limit = points . points [ i ] . starts . next ; for ( int j = 0 ; j < limit ; j += 3 ) { int dest = transitions [ j ] ; statesSet . incr ( dest ) ; accCount += a . isAccept ( dest ) ? 1 : 0 ; } lastPoint = point ; points . points [ i ] . starts . next = 0 ; } points . reset ( ) ; assert statesSet . upto == 0 : "upto=" + statesSet . upto ; } Automaton result = b . finish ( ) ; assert result . isDeterministic ( ) ; return result ; }
target:  Determinizes the given automaton. <p> Worst case complexity: exponential in number of states.