DeterminizeIDPDAPart.hxx

Go to the documentation of this file.

 
#include <ext/algorithm>
 
#include <alib/deque>
 
#include <automaton/PDA/InputDrivenNPDA.h>
 
namespace automaton {
 
namespace determinize {
 
template < class InputSymbolType, class PushdownSymbolType, class StateType >
automaton::InputDrivenDPDA < InputSymbolType, PushdownSymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::InputDrivenNPDA < InputSymbolType, PushdownSymbolType, StateType > & npda ) {
     // 1, 4
    ext::set < StateType > initialState;
    initialState.insert ( npda.getInitialState ( ) );
    automaton::InputDrivenDPDA < InputSymbolType, PushdownSymbolType, ext::set < StateType > > res ( initialState, npda.getInitialSymbol ( ) );
 
    res.setInputAlphabet ( npda.getInputAlphabet ( ) );
    res.setPushdownStoreAlphabet ( npda.getPushdownStoreAlphabet ( ) );
    res.setPushdownStoreOperations ( npda.getPushdownStoreOperations ( ) );
 
     // 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 InputSymbolType & input : npda.getInputAlphabet ( ) ) {
            ext::set < StateType > dfaState;
 
            for ( StateType nfaState : state ) {
                auto range = npda.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 = npda.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 */