Normalize.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/DFA.h>
#include <automaton/FSM/CompactDFA.h>
#include <automaton/TA/DFTA.h>
#include <automaton/PDA/DPDA.h>
#include <automaton/PDA/RealTimeHeightDeterministicDPDA.h>
 
namespace automaton {
 
namespace simplify {
 
class Normalize {
public:
    template < class SymbolType, class StateType >
    static automaton::DFA < SymbolType, unsigned > normalize(const automaton::DFA < SymbolType, StateType > & fsm);
 
    template < class SymbolType, class StateType >
    static automaton::CompactDFA < SymbolType, unsigned > normalize ( const automaton::CompactDFA < SymbolType, StateType > & fsm );
 
    template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
    static automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, unsigned, unsigned > normalize ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & pda );
 
    template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
    static automaton::DPDA < InputSymbolType, unsigned, unsigned > normalize(const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & pda);
 
    template < class SymbolType, class StateType >
    static automaton::DFTA < SymbolType, unsigned > normalize ( const automaton::DFTA < SymbolType, StateType > & fta );
};
 
template < class SymbolType, class StateType >
automaton::DFA < SymbolType, unsigned > Normalize::normalize(const automaton::DFA < SymbolType, StateType > & fsm) {
    unsigned counter = 0;
    ext::map < StateType, unsigned > normalizationData;
    ext::deque < StateType > processingData;
 
    normalizationData.insert(std::make_pair(fsm.getInitialState(), counter++));
    processingData.push_back(fsm.getInitialState());
 
    while(!processingData.empty()) {
        StateType current = std::move ( processingData.front() );
        processingData.pop_front();
 
        // Transitions are trivialy sorted by input symbol (from state is the same)
        for(const std::pair < const ext::pair < StateType, SymbolType >, StateType > & transition : fsm.getTransitionsFromState(current) ) {
            if(normalizationData.find(transition.second) == normalizationData.end()) {
                normalizationData.insert ( std::make_pair ( transition.second, counter++ ) );
                processingData.push_back ( transition.second );
            }
        }
    }
 
    if(normalizationData.size() != fsm.getStates().size()) {
        throw exception::CommonException("Automaton normalize require minimal deterministic finite automaton");
    }
 
    automaton::DFA < SymbolType, unsigned > result( normalizationData.find ( fsm.getInitialState ( ) )->second );
 
    result.setInputAlphabet(fsm.getInputAlphabet());
 
    for(const StateType & state : fsm.getStates ( ) ) {
        result.addState ( normalizationData.find ( state )->second );
    }
 
    for(const StateType & finalState : fsm.getFinalStates ( ) ) {
        result.addFinalState( normalizationData.find ( finalState )->second );
    }
 
    for(const std::pair < const ext::pair < StateType, SymbolType >, StateType > & transition : fsm.getTransitions ( ) ) {
        result.addTransition ( normalizationData.find ( transition.first.first )->second, transition.first.second, normalizationData.find ( transition.second )->second );
    }
 
    return result;
}
 
template < class SymbolType, class StateType >
automaton::CompactDFA < SymbolType, unsigned > Normalize::normalize ( const automaton::CompactDFA < SymbolType, StateType > & fsm ) {
    unsigned counter = 0;
    ext::map < StateType, unsigned > normalizationData;
    ext::deque < StateType > processingData;
 
    normalizationData.insert ( std::make_pair ( fsm.getInitialState ( ), counter ++ ) );
    processingData.push_back ( fsm.getInitialState ( ) );
 
    while ( ! processingData.empty ( ) ) {
        StateType current = std::move ( processingData.front ( ) );
        processingData.pop_front ( );
 
        // Transitions are trivialy sorted by input sequence (from state is the same)
        for ( const std::pair < const ext::pair < StateType, ext::vector < SymbolType > >, StateType > & transition : fsm.getTransitionsFromState ( current ) ) {
            if ( normalizationData.find ( transition.second ) == normalizationData.end ( ) ) {
                normalizationData.insert ( std::make_pair ( transition.second, counter ++ ) );
                processingData.push_back ( transition.second );
            }
        }
    }
 
    if ( normalizationData.size ( ) != fsm.getStates ( ).size ( ) ) {
        throw exception::CommonException ( "Automaton normalize require minimal deterministic finite automaton" );
    }
 
    automaton::CompactDFA < SymbolType, unsigned > result ( normalizationData.find ( fsm.getInitialState ( ) )->second );
 
    result.setInputAlphabet ( fsm.getInputAlphabet ( ) );
 
    for ( const StateType & state : fsm.getStates ( ) ) {
        result.addState ( normalizationData.find ( state )->second );
    }
 
    for ( const StateType & finalState : fsm.getFinalStates ( ) ) {
        result.addFinalState( normalizationData.find ( finalState )->second );
    }
 
    for ( const std::pair < const ext::pair < StateType, ext::vector < SymbolType > >, StateType > & transition : fsm.getTransitions ( ) ) {
        result.addTransition ( normalizationData.find ( transition.first.first )->second, transition.first.second, normalizationData.find ( transition.second )->second );
    }
 
    return result;
}
 
template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, unsigned, unsigned > Normalize::normalize ( const automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & pda ) {
    unsigned counterState = 0;
    ext::map< StateType, unsigned > normalizationDataState;
    unsigned counterSymbol = 0;
    ext::map < InputSymbolType, unsigned > normalizationDataSymbol;
    ext::deque < StateType > processingData;
 
    normalizationDataState.insert(std::make_pair(pda.getInitialState(), counterState++));
    normalizationDataSymbol.insert(std::make_pair(pda.getBottomOfTheStackSymbol(), counterSymbol++));
    processingData.push_back(pda.getInitialState());
 
    while(!processingData.empty()) {
        StateType current = std::move ( processingData.front() );
        processingData.pop_front();
 
        for ( const std::pair < const ext::pair < StateType, common::symbol_or_epsilon < InputSymbolType > >, ext::pair < StateType, PushdownStoreSymbolType > > & transition : pda.getCallTransitions().equal_range ( ext::slice_comp ( current ) ) ) {
            if ( ! normalizationDataState.contains ( transition.second.first ) ) {
                normalizationDataState.insert ( std::make_pair ( transition.second.first, counterState ++ ) );
                processingData.push_back ( transition.second.first );
            }
            if ( ! normalizationDataSymbol.contains ( transition.second.second ) ) {
                normalizationDataSymbol.insert ( std::make_pair ( transition.second.second, counterSymbol ++ ) );
            }
        }
        for ( const std::pair < const ext::pair < StateType, common::symbol_or_epsilon < InputSymbolType > >, StateType > & transition : pda.getLocalTransitions().equal_range ( ext::slice_comp ( current ) ) ) {
            if ( ! normalizationDataState.contains ( transition.second ) ) {
                normalizationDataState.insert ( std::make_pair ( transition.second, counterState ++ ) );
                processingData.push_back ( transition.second );
            }
        }
        bool allDone = true;
        for ( const std::pair < const ext::tuple < StateType, common::symbol_or_epsilon < InputSymbolType >, PushdownStoreSymbolType >, StateType > & transition : pda.getReturnTransitions().equal_range ( ext::slice_comp ( current ) ) ) {
            if ( normalizationDataSymbol.contains ( std::get < 2 > ( transition.first ) ) ) {
                if ( ! normalizationDataState.contains ( transition.second ) ) {
                    normalizationDataState.insert ( std::make_pair ( transition.second, counterState ++ ) );
                    processingData.push_back ( transition.second );
                }
            } else {
                allDone = false;
            }
        }
        if ( ! allDone ) {
            processingData.push_back ( std::move ( current ) );
        }
    }
 
    if(normalizationDataState.size() != pda.getStates().size() || normalizationDataSymbol.size() != pda.getPushdownStoreAlphabet().size()) {
        throw exception::CommonException("Automaton normalize require connected deterministic pushdown automaton");
    }
 
    automaton::RealTimeHeightDeterministicDPDA < InputSymbolType, unsigned, unsigned > result ( normalizationDataState.find ( pda.getInitialState ( ) )->second, normalizationDataSymbol.find ( pda.getBottomOfTheStackSymbol ( ) )->second );
    result.setInputAlphabet(pda.getInputAlphabet());
 
    for(const DefaultSymbolType & symbol : pda.getPushdownStoreAlphabet())
        result.addPushdownStoreSymbol(normalizationDataSymbol.find(symbol)->second);
 
    for(const DefaultStateType & state : pda.getStates())
        result.addState ( normalizationDataState.find(state)->second);
 
    for(const DefaultStateType & state : pda.getFinalStates())
        result.addFinalState ( normalizationDataState.find(state)->second );
 
    for ( const std::pair < const ext::pair < StateType, common::symbol_or_epsilon < InputSymbolType > >, ext::pair < StateType, PushdownStoreSymbolType > > & transition : pda.getCallTransitions()) {
        result.addCallTransition ( normalizationDataState.at ( transition.first.first ), transition.first.second, normalizationDataState.at ( transition.second.first ), normalizationDataSymbol.at ( transition.second.second ) );
    }
 
    for(const auto & transition : pda.getLocalTransitions()) {
        result.addLocalTransition ( normalizationDataState.at ( transition.first.first ), transition.first.second, normalizationDataState.at ( transition.second ) );
    }
 
    for(const auto & transition : pda.getReturnTransitions()) {
        result.addReturnTransition ( normalizationDataState.at ( std::get < 0 > ( transition.first ) ), std::get < 1 > ( transition.first ), normalizationDataSymbol.at ( std::get < 2 > ( transition.first ) ), normalizationDataState.at ( transition.second ) );
    }
 
    return result;
}
 
template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
automaton::DPDA < InputSymbolType, unsigned, unsigned > Normalize::normalize(const automaton::DPDA < InputSymbolType, PushdownStoreSymbolType, StateType > & pda) {
    unsigned counterState = 0;
    ext::map< StateType, unsigned > normalizationDataState;
    unsigned counterSymbol = 0;
    ext::map < InputSymbolType, unsigned > normalizationDataSymbol;
    ext::deque < StateType > processingData;
 
    normalizationDataState.insert(std::make_pair(pda.getInitialState(), counterState++));
    normalizationDataSymbol.insert(std::make_pair(pda.getInitialSymbol(), counterSymbol++));
    processingData.push_back(pda.getInitialState());
 
    while(!processingData.empty()) {
        StateType current = std::move ( processingData.front() );
        processingData.pop_front();
 
        ext::map < std::pair < common::symbol_or_epsilon < InputSymbolType >, ext::vector < unsigned > >, std::pair < StateType, ext::vector < PushdownStoreSymbolType > > > transform;
        bool stateFinished = true;
        // For each transition from state current
        for ( const std::pair < const ext::tuple < StateType, common::symbol_or_epsilon < InputSymbolType >, ext::vector < PushdownStoreSymbolType > >, ext::pair < StateType, ext::vector < PushdownStoreSymbolType > > > & iter : pda.getTransitionsFromState(current)) {
            // look whether all pop symbols are already transformed
            if(std::all_of(std::get<2>(iter.first).begin(), std::get<2>(iter.first).end(), [&](const PushdownStoreSymbolType& symbol) { return normalizationDataSymbol.find(symbol) != normalizationDataSymbol.end(); })) {
                ext::vector < unsigned > transformedSymbols;
                // if so compute vector of transformed poped symbol -- this can be compared to other vectors of transformed symbols and the order can be trusted
                for(const PushdownStoreSymbolType& symbol : std::get<2> ( iter.first ) ) {
                    transformedSymbols.push_back(normalizationDataSymbol.find(symbol)->second);
                }
 
                // then first order is by input symbol and the second is this vector transfomed symbols
                transform.insert(std::make_pair(std::make_pair(std::get<1>(iter.first), transformedSymbols), iter.second));
            } else {
                stateFinished = false;
            }
        }
        // if there was a single transition with undefined transformation for pop symbol process this state again later
        if(!stateFinished) {
            processingData.push_back(std::move ( current ) );
        }
        // now transitions are trivially sorted by input symbol and the already transformed symbols
 
        // for each pair state, pushed symbols in order given by input symbol and transformed pop symbols
        for(const auto& iter : transform) {
            const auto& iters = iter.second;
            // if the state is new assign a unique number to it and mark it for processing
            if( normalizationDataState.find(iters.first) == normalizationDataState.end() ) {
                normalizationDataState.insert(std::make_pair(iters.first, counterState++));
                processingData.push_back(iters.first);
            }
            // if the symbols in order given by order of pushing are new assign a unique number to them
            for(const PushdownStoreSymbolType & iter2 : iters.second) {
                if( normalizationDataSymbol.find(iter2) == normalizationDataSymbol.end() ) {
                    normalizationDataSymbol.insert(std::make_pair(iter2, counterSymbol++));
                }
            }
        }
    }
 
    if(normalizationDataState.size() != pda.getStates().size() || normalizationDataSymbol.size() != pda.getPushdownStoreAlphabet().size()) {
        throw exception::CommonException("Automaton normalize require connected deterministic pushdown automaton");
    }
 
    automaton::DPDA < InputSymbolType, unsigned, unsigned > result ( normalizationDataState.find ( pda.getInitialState ( ) )->second, normalizationDataSymbol.find ( pda.getInitialSymbol ( ) )->second );
    result.setInputAlphabet(pda.getInputAlphabet());
 
    for(const DefaultSymbolType & symbol : pda.getPushdownStoreAlphabet())
        result.addPushdownStoreSymbol(normalizationDataSymbol.find(symbol)->second);
 
    for(const DefaultStateType & state : pda.getStates())
        result.addState ( normalizationDataState.find(state)->second);
 
    for(const DefaultStateType & state : pda.getFinalStates())
        result.addFinalState ( normalizationDataState.find(state)->second );
 
    for(const auto & transition : pda.getTransitions()) {
        ext::vector<unsigned> pop;
        for(const auto& elem : std::get<2>(transition.first)) {
            pop.push_back(normalizationDataSymbol.find(elem)->second);
        }
        ext::vector<unsigned> push;
        for(const auto& elem : transition.second.second) {
            push.push_back(normalizationDataSymbol.find(elem)->second);
        }
        result.addTransition ( normalizationDataState.find(std::get<0>(transition.first))->second, std::get<1>(transition.first), pop, normalizationDataState.find(transition.second.first)->second, push);
    }
 
    return result;
}
 
template < class SymbolType, class StateType >
automaton::DFTA < SymbolType, unsigned > Normalize::normalize ( const automaton::DFTA < SymbolType, StateType > & fta ) {
    unsigned counter = 0;
    ext::map < StateType, unsigned > normalizationData;
 
    auto isNormalized = [ & normalizationData ] ( const StateType & origName ) {
        return normalizationData.count ( origName ) > 0;
    };
 
    ext::map < ext::pair < common::ranked_symbol < SymbolType >, ext::vector < unsigned > >, StateType > processing;
    do {
        processing.clear ( );
 
        // accumulate all transitions from normalized states to not yet normalized state
        for ( const auto & transition : fta.getTransitions ( ) )
            if ( std::all_of ( transition.first.second.begin ( ), transition.first.second.end ( ), isNormalized ) && ! isNormalized ( transition.second ) ) {
                ext::vector < unsigned > from;
                for ( const StateType & state : transition.first.second )
                    from.push_back ( normalizationData.at ( state ) );
 
                processing.insert ( ext::make_pair ( transition.first.first, from ), transition.second );
            }
 
        for ( const std::pair < const ext::pair < common::ranked_symbol < SymbolType >, ext::vector < unsigned > >, StateType > & transition : processing )
            // accumuated transition inducing normalization might have contained two or more transitions to the same state, but we want to normalize only once
            if ( ! isNormalized ( transition.second ) )
                normalizationData [ transition.second ] = counter ++;
 
    } while ( !processing.empty ( ) );
 
    if ( normalizationData.size ( ) != fta.getStates ( ).size ( ) ) {
        throw exception::CommonException ( "Automaton normalize require minimal deterministic finite tree automaton" );
    }
 
    automaton::DFTA < SymbolType, unsigned > result;
    result.setInputAlphabet ( fta.getInputAlphabet ( ) );
 
    for ( const StateType & state : fta.getStates ( ) ) {
        result.addState ( normalizationData.at ( state ) );
    }
 
    for ( const StateType & finalState : fta.getFinalStates ( ) ) {
        result.addFinalState ( normalizationData.at ( finalState ) );
    }
 
    for ( const auto & transition : fta.getTransitions ( ) ) {
        ext::vector < unsigned > prevStates;
        for ( const StateType & prev : transition.first.second )
            prevStates.push_back ( normalizationData.at ( prev ) );
 
        result.addTransition ( transition.first.first, prevStates, normalizationData.at ( transition.second ) );
    }
 
    return result;
}
 
} /* namespace simplify */
 
} /* namespace automaton */