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;
}

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 ; }
determinizes the given automaton . < p > worst case complexity : exponential in number of states .
