UnreachableStatesRemover.h

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#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 <automaton/TA/ArcFactoredDeterministicZAutomaton.h>
#include <automaton/TA/ArcFactoredNondeterministicZAutomaton.h>
#include <automaton/TA/DFTA.h>
 
#include <automaton/properties/ReachableStates.h>
 
namespace automaton {
 
namespace simplify {
 
class UnreachableStatesRemover {
public:
    template < class T >
    requires isDFA < T > || isNFA < T > || isEpsilonNFA < T > || isCompactNFA < T > || isExtendedNFA < 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 >
    requires isDFTA < T > || isNFTA < T >
    static T remove ( const T & fta );
 
    template < class T >
    requires isAFDZA < T > || isAFNZA < T >
    static T remove( const T & afza );
};
 
template < class T >
requires isDFA < T > || isNFA < T > || isEpsilonNFA < T > || isCompactNFA < T > || isExtendedNFA < T >
T UnreachableStatesRemover::remove ( const T & fsm ) {
    using StateType = typename T::StateType;
 
    // 1a
    ext::set<StateType> Qa = automaton::properties::ReachableStates::reachableStates( fsm );
 
    // 2
    T M(fsm.getInitialState());
 
    M.setStates( Qa );
    M.setInputAlphabet( fsm.getInputAlphabet( ) );
 
    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> finalStates;
    std::set_intersection( fsm.getFinalStates( ).begin(), fsm.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( finalStates, finalStates.begin( ) ) );
    M.setFinalStates( finalStates );
 
    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::ReachableStates::reachableStates( fsm );
 
    // 2
    automaton::MultiInitialStateNFA < SymbolType, StateType > M;
 
    M.setStates( Qa );
    M.setInitialStates( fsm.getInitialStates() );
    M.setInputAlphabet( fsm.getInputAlphabet( ) );
 
    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> finalStates;
    std::set_intersection( fsm.getFinalStates( ).begin(), fsm.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( finalStates, finalStates.begin( ) ) );
    M.setFinalStates( finalStates );
 
    return M;
}
 
template < class T >
requires isDFTA < T > || isNFTA < T >
T UnreachableStatesRemover::remove( const T & fta ) {
    using StateType = typename T::StateType;
 
    // 1a
    ext::set<StateType> Qa = automaton::properties::ReachableStates::reachableStates( fta );
 
    // 2
    T M;
 
    M.setStates( Qa );
    M.setInputAlphabet( fta.getInputAlphabet( ) );
 
    for( const auto & transition : fta.getTransitions( ) )
        if( std::all_of ( transition.first.second.begin ( ), transition.first.second.end ( ), [ & ] ( const StateType & state ) { return Qa.count ( state ); } ) )
            M.addTransition ( transition.first.first, transition.first.second, transition.second );
 
    ext::set<StateType> finalStates;
    std::set_intersection( fta.getFinalStates( ).begin(), fta.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( finalStates, finalStates.begin( ) ) );
    M.setFinalStates( std::move ( finalStates ) );
 
    return M;
}
 
template < class T >
requires isAFDZA < T > || isAFNZA < T >
T UnreachableStatesRemover::remove( const T & afza ) {
    using StateType = typename T::StateType;
    using SymbolType = typename T::SymbolType;
 
    // 1a
    auto Qa = automaton::properties::ReachableStates::reachableStates( afza );
 
    // 2
    T M;
 
    M.setStates( Qa );
    M.setInputAlphabet( afza.getInputAlphabet( ) );
 
    for( const auto & transition : afza.getTransitions( ) ) {
        if ( transition.first.template is < SymbolType > ( ) && Qa.contains ( transition.second ) ) {
            M.addTransition ( transition.first, transition.second );
        } else if ( transition.first.template is < ext::pair < StateType, StateType > > ( ) ) {
            const auto& [ q1, q2 ] = transition.first.template get < ext::pair < StateType, StateType > > ( );
            if ( Qa.contains ( q1 ) && Qa.contains ( q2 ) && Qa.contains ( transition.second ) ) {
                M.addTransition ( transition.first, transition.second );
            }
        }
    }
 
    ext::set<StateType> finalStates;
    std::set_intersection( afza.getFinalStates( ).begin(), afza.getFinalStates( ).end(), Qa.begin( ), Qa.end( ), std::inserter( finalStates, finalStates.begin( ) ) );
    M.setFinalStates( std::move ( finalStates ) );
 
    return M;
}
 
} /* namespace simplify */
 
} /* namespace automaton */