UselessStatesRemover.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/properties/UsefulStates.h>
 
#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>
 
namespace automaton {
 
namespace simplify {
 
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 SymbolType, class StateType >
    static automaton::DFTA < SymbolType, StateType > remove( const automaton::DFTA < SymbolType, StateType > & fta );
 
    template < class SymbolType, class StateType >
    static automaton::NFTA < SymbolType, StateType > remove( const automaton::NFTA < SymbolType, StateType > & fta );
 
    template < class SymbolType, class StateType >
    static automaton::ArcFactoredNondeterministicZAutomaton < SymbolType, StateType > remove( const automaton::ArcFactoredNondeterministicZAutomaton < SymbolType, StateType > & afza );
 
    template < class SymbolType, class StateType >
    static automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > remove( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & afza );
};
 
template < class T >
T UselessStatesRemover::remove( const T & fsm ) {
    using StateType = typename T::StateType;
 
    // 1.
    ext::set<StateType> Qu = automaton::properties::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::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;
}
 
template < class SymbolType, class StateType >
automaton::DFTA < SymbolType, StateType > UselessStatesRemover::remove( const automaton::DFTA < SymbolType, StateType > & fta ) {
    // 1.
    ext::set<StateType> Qu = automaton::properties::UsefulStates::usefulStates( fta );
 
    // 2.
    automaton::DFTA < SymbolType, StateType > M;
 
    for( const auto & a : fta.getInputAlphabet( ) )
        M.addInputSymbol( a );
 
    if(Qu.empty ( )) {
        return M;
    }
 
    for( const auto & q : Qu )
        M.addState( q );
 
    for( const auto & t : fta.getTransitions( ) )
        if( Qu.count( t.second ) )
            M.addTransition( t.first.first, t.first.second, t.second );
 
    for( const auto & q : fta.getFinalStates( ) )
        M.addFinalState( q );
 
    return M;
}
 
template < class SymbolType, class StateType >
automaton::NFTA < SymbolType, StateType > UselessStatesRemover::remove( const automaton::NFTA < SymbolType, StateType > & fta ) {
    // 1.
    ext::set<StateType> Qu = automaton::properties::UsefulStates::usefulStates( fta );
 
    // 2.
    automaton::NFTA < SymbolType, StateType > M;
 
    for( const auto & a : fta.getInputAlphabet( ) )
        M.addInputSymbol( a );
 
    if(Qu.empty ( )) {
        return M;
    }
 
    for( const auto & q : Qu )
        M.addState( q );
 
    for( const auto & t : fta.getTransitions( ) )
        if( Qu.count( t.second ) )
            M.addTransition( t.first.first, t.first.second, t.second );
 
    for( const auto & q : fta.getFinalStates( ) )
        M.addFinalState( q );
 
    return M;
}
 
template < class SymbolType, class StateType >
automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > UselessStatesRemover::remove( const automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > & afza ) {
    auto Qu = automaton::properties::UsefulStates::usefulStates ( afza );
 
    automaton::ArcFactoredDeterministicZAutomaton < SymbolType, StateType > M;
    M.setInputAlphabet ( afza.getInputAlphabet ( ) );
    M.setStates ( Qu );
 
    if ( M.getStates ( ).empty ( ) ) {
        return M;
    }
 
    for ( const auto & t : afza.getTransitions( ) )
        if ( Qu.count ( t.second ) )
            M.addTransition ( t.first, t.second );
 
    M.setFinalStates ( afza.getFinalStates ( ) );
    return M;
}
 
template < class SymbolType, class StateType >
automaton::ArcFactoredNondeterministicZAutomaton < SymbolType, StateType > UselessStatesRemover::remove( const automaton::ArcFactoredNondeterministicZAutomaton < SymbolType, StateType > & afza ) {
    auto Qu = automaton::properties::UsefulStates::usefulStates ( afza );
 
    automaton::ArcFactoredNondeterministicZAutomaton < SymbolType, StateType > M;
    M.setInputAlphabet ( afza.getInputAlphabet ( ) );
    M.setStates ( Qu );
 
    if ( M.getStates ( ).empty ( ) ) {
        return M;
    }
 
    for ( const auto & t : afza.getTransitions( ) )
        if ( Qu.count ( t.second ) )
            M.addTransition ( t.first, t.second );
 
    M.setFinalStates ( afza.getFinalStates ( ) );
    return M;
}
 
} /* namespace simplify */
 
} /* namespace automaton */