EpsilonRemoverIncoming.h

Go to the documentation of this file.

 
#pragma once
 
#include <map>
#include <algorithm>
 
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>
 
#include "../../properties/efficient/AllEpsilonClosure.h"
 
namespace automaton {
 
namespace simplify {
 
namespace efficient {
 
class EpsilonRemoverIncoming {
public:
    template < class SymbolType, class StateType >
    static automaton::NFA < SymbolType, StateType > remove( const automaton::EpsilonNFA < SymbolType, StateType > & fsm );
    template < class SymbolType, class StateType >
    static automaton::MultiInitialStateNFA < SymbolType, StateType > remove( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm );
    template < class SymbolType, class StateType >
    static automaton::NFA < SymbolType, StateType > remove( const automaton::NFA < SymbolType, StateType > & fsm );
    template < class SymbolType, class StateType >
    static automaton::DFA < SymbolType, StateType > remove ( const automaton::DFA < SymbolType, StateType > & fsm );
};
 
template < class SymbolType, class StateType >
automaton::DFA < SymbolType, StateType > EpsilonRemoverIncoming::remove ( const automaton::DFA < SymbolType, StateType > & fsm ) {
    return fsm;
}
 
template < class SymbolType, class StateType >
automaton::MultiInitialStateNFA < SymbolType, StateType > EpsilonRemoverIncoming::remove ( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm ) {
    return fsm;
}
 
template < class SymbolType, class StateType >
automaton::NFA < SymbolType, StateType > EpsilonRemoverIncoming::remove ( const automaton::NFA < SymbolType, StateType > & fsm ) {
    return fsm;
}
 
template < class SymbolType, class StateType >
automaton::NFA < SymbolType, StateType > EpsilonRemoverIncoming::remove ( const automaton::EpsilonNFA < SymbolType, StateType > & fsm ) {
    automaton::NFA < SymbolType, StateType > res ( fsm.getInitialState ( ) );
 
    res.setStates ( fsm.getStates ( ) );
    res.setInputAlphabet ( fsm.getInputAlphabet ( ) );
 
    ext::map < StateType, ext::set < StateType > > closures = automaton::properties::efficient::AllEpsilonClosure::allEpsilonClosure ( fsm );
 
    ext::multimap < ext::pair < StateType, SymbolType >, StateType > origTransitions = fsm.getSymbolTransitions ( );
 
    for ( const auto & from : fsm.getStates ( ) )
        for ( const auto & fromClosure : closures [ from ] )
            for ( const auto & symbol : fsm.getInputAlphabet ( ) ) {
                auto transitions = origTransitions.equal_range ( ext::make_pair ( fromClosure, symbol ) );
 
                for ( const auto & transition : transitions )
                    res.addTransition( from, symbol, transition.second );
            }
 
    const ext::set < StateType > & F = fsm.getFinalStates ( );
    for ( const auto & q : res.getStates ( ) ) {
        const ext::set < StateType > & cl = closures [ q ];
 
        if ( ! ext::excludes ( F.begin ( ), F.end ( ), cl.begin ( ), cl.end ( ) ) )
            res.addFinalState ( q );
    }
 
    return res;
}
 
} /* namespace efficient */
 
} /* namespace simplify */
 
} /* namespace automaton */