public DFAState < T > constructDFA ( Scope < DFAState < T > > dfaScope ) { Map < Set < NFAState < T > > , DFAState < T > > all = new HashMap <> ( ) ; Deque < DFAState < T > > unmarked = new ArrayDeque <> ( ) ; Set < NFAState < T > > startSet = epsilonClosure ( dfaScope ) ; DFAState < T > startDfa = new DFAState <> ( dfaScope , startSet ) ; all . put ( startSet , startDfa ) ; unmarked . add ( startDfa ) ; while ( ! unmarked . isEmpty ( ) ) { DFAState < T > dfa = unmarked . pop ( ) ; for ( CharRange c : dfa . possibleMoves ( ) ) { Set < NFAState < T >> moveSet = dfa . nfaTransitsFor ( c ) ; if ( ! moveSet . isEmpty ( ) ) { Set < NFAState < T >> newSet = epsilonClosure ( dfaScope , moveSet ) ; DFAState < T > ndfa = all . get ( newSet ) ; if ( ndfa == null ) { ndfa = new DFAState <> ( dfaScope , newSet ) ; all . put ( newSet , ndfa ) ; unmarked . add ( ndfa ) ; } dfa . addTransition ( c , ndfa ) ; } } } // optimize for ( DFAState < T > dfa : all . values ( ) ) { dfa . removeTransitionsFromAcceptImmediatelyStates ( ) ; } for ( DFAState < T > dfa : all . values ( ) ) { dfa . removeDeadEndTransitions ( ) ; } for ( DFAState < T > dfa : startDfa ) { dfa . optimizeTransitions ( ) ; } return startDfa ; }
Construct a dfa by using this state as starting state .