DeterminizeZAutomataPart.hxx

Go to the documentation of this file.

 
#include <ext/algorithm>
 
#include <alib/deque>
#include <alib/set>
 
namespace automaton {
 
namespace determinize {
 
template < class SymbolType, class StateType >
automaton::ArcFactoredDeterministicZAutomaton < SymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::ArcFactoredNondeterministicZAutomaton < SymbolType, StateType > & automaton ) {
    automaton::ArcFactoredDeterministicZAutomaton < SymbolType, ext::set < StateType > > res;
    res.setInputAlphabet ( automaton.getInputAlphabet ( ) );
 
    for ( const SymbolType & input : automaton.getInputAlphabet ( ) ) {
        auto range = automaton.getTransitions ( ).equal_range ( input );
 
        ext::set < StateType > dfaState;
        for ( auto & transition : range )
            dfaState.insert ( transition.second );
 
        res.addState ( dfaState );
 
        res.addTransition ( input, dfaState );
    }
 
    bool changed;
    do {
        changed = false;
        for ( const ext::set < StateType > & dfaState1 : res.getStates ( ) ) {
            for ( const ext::set < StateType > & dfaState2 : res.getStates ( ) ) {
                ext::set < StateType > dfaState;
                for ( const StateType & nfaState1 : dfaState1 ) {
                    for ( const StateType & nfaState2 : dfaState2 ) {
 
                        auto range = automaton.getTransitions ( ).equal_range ( ext::make_pair ( nfaState1, nfaState2 ) );
                        for ( auto & transition : range )
                            dfaState.insert ( transition.second );
                    }
                }
 
                changed |= res.addState ( dfaState );
 
                res.addTransition ( ext::make_pair ( dfaState1, dfaState2 ), std::move ( dfaState ) );
            }
        }
    } while ( changed );
 
    const ext::set < StateType > & finalLabels = automaton.getFinalStates();
    for ( const ext::set < StateType > & dfaState : res.getStates ( ) )
        if ( ! ext::excludes ( finalLabels.begin ( ), finalLabels.end ( ), dfaState.begin ( ), dfaState.end ( ) ) )
            res.addFinalState ( dfaState );
 
    return res;
}
 
} /* namespace determinize */
 
} /* namespace automaton */