UselessStatesRemover.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/UsefulStates.h"
 
namespace automaton {
 
namespace simplify {
 
namespace efficient {
 
class UselessStatesRemover {
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 UselessStatesRemover::remove( const T & fsm ) {
    using StateType = typename T::StateType;
 
    // 1.
    ext::set<StateType> Qu = automaton::properties::efficient::UsefulStates::usefulStates( fsm );
 
    // 2.
    T M(fsm.getInitialState());
 
    for( const auto & a : fsm.getInputAlphabet( ) )
        M.addInputSymbol( a );
 
    if(Qu.empty ( )) {
        return M;
    }
 
    for( const auto & q : Qu )
        M.addState( q );
 
    for( const auto & t : fsm.getTransitions( ) )
        if( /* this part is not needed Qu.count( t.first.first ) && */ Qu.count( t.second ) )
            M.addTransition( t.first.first, t.first.second, t.second );
 
    for( const auto & q : fsm.getFinalStates( ) )
        M.addFinalState( q );
 
    return M;
}
 
template < class SymbolType, class StateType >
automaton::MultiInitialStateNFA < SymbolType, StateType > UselessStatesRemover::remove( const automaton::MultiInitialStateNFA < SymbolType, StateType > & fsm ) {
    // 1.
    ext::set<StateType> Qu = automaton::properties::efficient::UsefulStates::usefulStates( fsm );
 
    // 2.
    automaton::MultiInitialStateNFA < SymbolType, StateType > M;
 
    for( const auto & a : fsm.getInputAlphabet( ) )
        M.addInputSymbol( a );
 
    if(Qu.empty ( )) {
        return M;
    }
 
    for( const auto & q : Qu )
        M.addState( q );
 
    for(const auto& init : fsm.getInitialStates()) {
        if( Qu.count(init) )
            M.addInitialState( init );
    }
 
    for( const auto & t : fsm.getTransitions( ) )
        if( Qu.count(t.second) )
            M.addTransition( t.first.first, t.first.second, t.second );
 
    for( const auto & q : fsm.getFinalStates( ) )
        M.addFinalState( q );
 
    return M;
}
 
} /* namespace efficient */
 
} /* namespace simplify */
 
} /* namespace automaton */