UnreachableStatesRemover.h

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <deque>
#include <set>
 
#include <automaton/FSM/ExtendedNFA.h>
#include <automaton/FSM/CompactNFA.h>
#include <automaton/FSM/EpsilonNFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>
 
#include "../../properties/efficient/ReachableStates.h"
 
namespace automaton {
 
namespace simplify {
 
namespace efficient {
 
class UnreachableStatesRemover {
public:
    template < class T >
    static T remove( const T & fsm );
    template < class SymbolType, class StateType >
    static automaton::MultiInitialStateNFA < SymbolType, StateType > remove( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm );
};
 
template < class T >
T UnreachableStatesRemover::remove ( const T & fsm ) {
    using StateType = typename T::StateType;
 
    // 1a
    ext::set<StateType> Qa = automaton::properties::efficient::ReachableStates::reachableStates( fsm );
 
    // 2
    T M(fsm.getInitialState());
 
    for( const auto & q : Qa )
        M.addState( q );
 
    for( const auto & a : fsm.getInputAlphabet( ) )
        M.addInputSymbol( a );
 
    for( const auto & transition : fsm.getTransitions( ) )
        if( Qa.count( transition.first.first ) )
            M.addTransition( transition.first.first, transition.first.second, transition.second );
 
    ext::set<StateType> intersect;
    std::set_intersection( fsm.getFinalStates( ).begin(), fsm.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( intersect, intersect.begin( ) ) );
    for( auto const & state : intersect )
        M.addFinalState( state );
 
    return M;
}
 
template < class SymbolType, class StateType >
automaton::MultiInitialStateNFA < SymbolType, StateType > UnreachableStatesRemover::remove( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm ) {
    // 1a
    ext::set<StateType> Qa = automaton::properties::efficient::ReachableStates::reachableStates( fsm );
 
    // 2
    automaton::MultiInitialStateNFA < SymbolType, StateType > M;
 
    for( const auto & q : Qa )
        M.addState( q );
 
    M.setInitialStates( fsm.getInitialStates() );
 
    for( const auto & a : fsm.getInputAlphabet( ) )
        M.addInputSymbol( a );
 
    for( const auto & transition : fsm.getTransitions( ) )
        if( Qa.count( transition.first.first ) )
            M.addTransition( transition.first.first, transition.first.second, transition.second );
 
    ext::set<StateType> intersect;
    std::set_intersection( fsm.getFinalStates( ).begin(), fsm.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( intersect, intersect.begin( ) ) );
    for( auto const & state : intersect )
        M.addFinalState( state );
 
    return M;
}
 
} /* namespace efficient */
 
} /* namespace simplify */
 
} /* namespace automaton */