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