DeterminizeNFTAPart.hxx

Go to the documentation of this file.

 
#include <ext/algorithm>
 
#include <alib/deque>
 
#include <automaton/TA/NFTA.h>
 
namespace automaton {
 
namespace determinize {
 
template < class SymbolType, class StateType >
void constructTransitions ( const common::ranked_symbol < SymbolType > & symbol, typename ext::vector < StateType >::const_iterator state, typename ext::vector < StateType >::const_iterator end, const StateType & rhs, const ext::multimap < StateType, ext::set < StateType > > & nftaStateToDftaStates, ext::vector < ext::set < StateType > > & transitionLHS, ext::map < ext::pair < common::ranked_symbol < SymbolType >, ext::vector < ext::set < StateType > > >, ext::set < StateType > > & resultTransition ) {
    if ( state == end ) {
        resultTransition [ ext::make_pair ( symbol, transitionLHS ) ].insert ( rhs );
    } else {
        for ( const std::pair < const StateType, ext::set < StateType > > & dftaState : nftaStateToDftaStates.equal_range ( * state ) ) {
            transitionLHS.push_back ( dftaState.second );
            constructTransitions ( symbol, std::next ( state ), end, rhs, nftaStateToDftaStates, transitionLHS, resultTransition );
            transitionLHS.pop_back ( );
        }
    }
}
 
template < class SymbolType, class StateType >
automaton::DFTA < SymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::NFTA < SymbolType, StateType > & nfta ) {
    automaton::DFTA < SymbolType, ext::set < StateType > > res;
 
    res.setInputAlphabet ( nfta.getInputAlphabet ( ) );
 
    ext::multimap < StateType, ext::set < StateType > > nftaStateToDftaStates; // each dfta state must be inserted only once to each nfta d-subset state
 
    for ( const auto & symbol : nfta.getInputAlphabet ( ) ) {
        if ( symbol.getRank ( ) != 0 )
            continue;
 
        ext::set < StateType > dftaState;
        ext::vector < StateType > source { };
        for ( const auto & transition : nfta.getTransitions ( ).equal_range ( ext::tie ( symbol, source ) ) )
            dftaState.insert ( transition.second );
 
        for ( const auto & state : dftaState )
            nftaStateToDftaStates.insert ( state, dftaState );
 
        res.addState ( dftaState );
 
        res.addTransition ( symbol, ext::vector < ext::set < StateType > > { }, dftaState );
    }
 
    bool added = true;
    while ( added ) {
        added = false;
 
        ext::map < ext::pair < common::ranked_symbol < SymbolType >, ext::vector < ext::set < StateType > > >, ext::set < StateType > > transitions;
 
        for ( const auto & transition : nfta.getTransitions ( ) ) {
            ext::vector < ext::set < StateType > > transitionLHS;
            constructTransitions ( transition.first.first, transition.first.second.begin ( ), transition.first.second.end ( ), transition.second, nftaStateToDftaStates, transitionLHS, transitions );
        }
 
        for ( const std::pair < const ext::pair < common::ranked_symbol < SymbolType >, ext::vector < ext::set < StateType > > >, ext::set < StateType > > & transition : transitions ) {
            if ( res.addState ( transition.second ) ) {
                added = true;
 
                for ( const auto & state : transition.second )
                    nftaStateToDftaStates.insert ( state, transition.second );
            }
            res.addTransition ( transition.first.first, transition.first.second, transition.second );
        }
 
    }
 
    const ext::set < StateType > & finalLabels = nfta.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 >
void constructTransitions ( const common::ranked_symbol < SymbolType > & symbol, typename ext::multiset < StateType >::const_iterator state, typename ext::multiset < StateType >::const_iterator end, const StateType & rhs, const ext::multimap < StateType, ext::set < StateType > > & nftaStateToDftaStates, ext::multiset < ext::set < StateType > > & transitionLHS, ext::map < ext::pair < common::ranked_symbol < SymbolType >, ext::multiset < ext::set < StateType > > >, ext::set < StateType > > & resultTransition ) {
    if ( state == end ) {
        resultTransition [ ext::make_pair ( symbol, transitionLHS ) ].insert ( rhs );
    } else {
        for ( const std::pair < const StateType, ext::set < StateType > > & dftaState : nftaStateToDftaStates.equal_range ( * state ) ) {
            transitionLHS.insert ( dftaState.second );
            constructTransitions ( symbol, std::next ( state ), end, rhs, nftaStateToDftaStates, transitionLHS, resultTransition );
            transitionLHS.erase ( transitionLHS.find ( dftaState.second ) );
        }
    }
}
 
template < class SymbolType, class StateType >
automaton::UnorderedDFTA < SymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::UnorderedNFTA < SymbolType, StateType > & nfta ) {
    automaton::UnorderedDFTA < SymbolType, ext::set < StateType > > res;
 
    res.setInputAlphabet ( nfta.getInputAlphabet ( ) );
 
    ext::multimap < StateType, ext::set < StateType > > nftaStateToDftaStates; // each dfta state must be inserted only once to each nfta d-subset state
 
    for ( const auto & symbol : nfta.getInputAlphabet ( ) ) {
        if ( symbol.getRank ( ) != 0 )
            continue;
 
        ext::set < StateType > dftaState;
        ext::multiset < StateType > source { };
        for ( const auto & transition : nfta.getTransitions ( ).equal_range ( ext::tie ( symbol, source ) ) )
            dftaState.insert ( transition.second );
 
        for ( const auto & state : dftaState )
            nftaStateToDftaStates.insert ( state, dftaState );
 
        res.addState ( dftaState );
 
        res.addTransition ( symbol, ext::multiset < ext::set < StateType > > { }, dftaState );
    }
 
    bool added = true;
    while ( added ) {
        added = false;
 
        ext::map < ext::pair < common::ranked_symbol < SymbolType >, ext::multiset < ext::set < StateType > > >, ext::set < StateType > > transitions;
 
        for ( const auto & transition : nfta.getTransitions ( ) ) {
            ext::multiset < ext::set < StateType > > transitionLHS;
            constructTransitions ( transition.first.first, transition.first.second.begin ( ), transition.first.second.end ( ), transition.second, nftaStateToDftaStates, transitionLHS, transitions );
        }
 
        for ( const std::pair < const ext::pair < common::ranked_symbol < SymbolType >, ext::multiset < ext::set < StateType > > >, ext::set < StateType > > & transition : transitions ) {
            if ( res.addState ( transition.second ) ) {
                added = true;
 
                for ( const auto & state : transition.second )
                    nftaStateToDftaStates.insert ( state, transition.second );
            }
            res.addTransition ( transition.first.first, transition.first.second, transition.second );
        }
 
    }
 
    const ext::set < StateType > & finalLabels = nfta.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 */