DeterminizeNFAPart.hxx

Go to the documentation of this file.

 
#include <ext/algorithm>
 
#include <alib/deque>
#include <alib/set>
 
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
 
namespace automaton {
 
namespace determinize {
 
template < class SymbolType, class StateType >
automaton::DFA < SymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::MultiInitialStateNFA < SymbolType, StateType > & nfa ) {
     // 1, 4
    ext::set < StateType > initialState = nfa.getInitialStates ( );
    automaton::DFA < SymbolType, ext::set < StateType > > res ( initialState );
 
    res.setInputAlphabet ( nfa.getInputAlphabet ( ) );
 
     // 2
    ext::deque < ext::set < StateType > > todo;
    todo.push_back ( std::move ( initialState ) );
 
    do {
         // 3a, c
        ext::set < StateType > state = std::move ( todo.front ( ) );
        todo.pop_front ( );
 
         // 3b
        for ( const SymbolType & input : nfa.getInputAlphabet ( ) ) {
            ext::set < StateType > dfaState;
 
            for ( StateType nfaState : state ) {
                auto range = nfa.getTransitions ( ).equal_range ( ext::make_pair ( std::move ( nfaState ), input ) );
 
                for ( auto & transition : range )
                    dfaState.insert ( transition.second );
            }
 
             // 4
            bool existed = !res.addState ( dfaState );
 
            if ( !existed ) todo.push_back ( dfaState );
 
             // 3b
            res.addTransition ( state, input, std::move ( dfaState ) );
        }
    } while ( !todo.empty ( ) );
 
     // 5
    const ext::set < StateType > & finalLabels = nfa.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;
}
 
template < class SymbolType, class StateType >
automaton::DFA < SymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::NFA < SymbolType, StateType > & nfa ) {
     // 1, 4
    ext::set < StateType > initialState;
    initialState.insert ( nfa.getInitialState ( ) );
    automaton::DFA < SymbolType, ext::set < StateType > > res ( initialState );
 
    res.setInputAlphabet ( nfa.getInputAlphabet ( ) );
 
     // 2
    ext::deque < ext::set < StateType > > todo;
    todo.push_back ( std::move ( initialState ) );
 
    do {
         // 3a, c
        ext::set < StateType > state = std::move ( todo.front ( ) );
        todo.pop_front ( );
 
         // 3b
        for ( const SymbolType & input : nfa.getInputAlphabet ( ) ) {
            ext::set < StateType > dfaState;
 
            for ( StateType nfaState : state ) {
                auto range = nfa.getTransitions ( ).equal_range ( ext::make_pair ( std::move ( nfaState ), input ) );
 
                for ( auto & transition : range )
                    dfaState.insert ( transition.second );
            }
 
             // 4
            bool existed = !res.addState ( dfaState );
 
            if ( !existed ) todo.push_back ( dfaState );
 
             // 3b
            res.addTransition ( state, input, std::move ( dfaState ) );
        }
    } while ( !todo.empty ( ) );
 
     // 5
    const ext::set < StateType > & finalLabels = nfa.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 */