static public Automaton intersection(Automaton a1,Automaton a2){
  if (a1 == a2) {
    return a1;
  }
  if (a1.getNumStates() == 0) {
    return a1;
  }
  if (a2.getNumStates() == 0) {
    return a2;
  }
  Transition[][] transitions1=a1.getSortedTransitions();
  Transition[][] transitions2=a2.getSortedTransitions();
  Automaton c=new Automaton();
  c.createState();
  LinkedList<StatePair> worklist=new LinkedList<>();
  HashMap<StatePair,StatePair> newstates=new HashMap<>();
  StatePair p=new StatePair(0,0,0);
  worklist.add(p);
  newstates.put(p,p);
  while (worklist.size() > 0) {
    p=worklist.removeFirst();
    c.setAccept(p.s,a1.isAccept(p.s1) && a2.isAccept(p.s2));
    Transition[] t1=transitions1[p.s1];
    Transition[] t2=transitions2[p.s2];
    for (int n1=0, b2=0; n1 < t1.length; n1++) {
      while (b2 < t2.length && t2[b2].max < t1[n1].min)       b2++;
      for (int n2=b2; n2 < t2.length && t1[n1].max >= t2[n2].min; n2++)       if (t2[n2].max >= t1[n1].min) {
        StatePair q=new StatePair(t1[n1].dest,t2[n2].dest);
        StatePair r=newstates.get(q);
        if (r == null) {
          q.s=c.createState();
          worklist.add(q);
          newstates.put(q,q);
          r=q;
        }
        int min=t1[n1].min > t2[n2].min ? t1[n1].min : t2[n2].min;
        int max=t1[n1].max < t2[n2].max ? t1[n1].max : t2[n2].max;
        c.addTransition(p.s,r.s,min,max);
      }
    }
  }
  c.finishState();
  return removeDeadStates(c);
}

static public Automaton intersection ( Automaton a1 , Automaton a2 ) { if ( a1 == a2 ) { return a1 ; } if ( a1 . getNumStates ( ) == 0 ) { return a1 ; } if ( a2 . getNumStates ( ) == 0 ) { return a2 ; } Transition [ ] [ ] transitions1 = a1 . getSortedTransitions ( ) ; Transition [ ] [ ] transitions2 = a2 . getSortedTransitions ( ) ; Automaton c = new Automaton ( ) ; c . createState ( ) ; LinkedList < StatePair > worklist = new LinkedList < > ( ) ; HashMap < StatePair , StatePair > newstates = new HashMap < > ( ) ; StatePair p = new StatePair ( 0 , 0 , 0 ) ; worklist . add ( p ) ; newstates . put ( p , p ) ; while ( worklist . size ( ) > 0 ) { p = worklist . removeFirst ( ) ; c . setAccept ( p . s , a1 . isAccept ( p . s1 ) && a2 . isAccept ( p . s2 ) ) ; Transition [ ] t1 = transitions1 [ p . s1 ] ; Transition [ ] t2 = transitions2 [ p . s2 ] ; for ( int n1 = 0 , b2 = 0 ; n1 < t1 . length ; n1 ++ ) { while ( b2 < t2 . length && t2 [ b2 ] . max < t1 [ n1 ] . min ) b2 ++ ; for ( int n2 = b2 ; n2 < t2 . length && t1 [ n1 ] . max >= t2 [ n2 ] . min ; n2 ++ ) if ( t2 [ n2 ] . max >= t1 [ n1 ] . min ) { StatePair q = new StatePair ( t1 [ n1 ] . dest , t2 [ n2 ] . dest ) ; StatePair r = newstates . get ( q ) ; if ( r == null ) { q . s = c . createState ( ) ; worklist . add ( q ) ; newstates . put ( q , q ) ; r = q ; } int min = t1 [ n1 ] . min > t2 [ n2 ] . min ? t1 [ n1 ] . min : t2 [ n2 ] . min ; int max = t1 [ n1 ] . max < t2 [ n2 ] . max ? t1 [ n1 ] . max : t2 [ n2 ] . max ; c . addTransition ( p . s , r . s , min , max ) ; } } } c . finishState ( ) ; return removeDeadStates ( c ) ; }
returns an automaton that accepts the intersection of the languages of the given automata . never modifies the input automata languages . < p > complexity : quadratic in number of states .
