AutomataConcatenation.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/NFA.h>
#include <automaton/FSM/DFA.h>
 
#include <label/InitialStateLabel.h>
 
namespace automaton::transform {
 
class AutomataConcatenation {
public:
    template < class AutomatonType >
    requires isDFA < AutomatonType > || isNFA < AutomatonType >
    static automaton::NFA < typename AutomatonType::SymbolType, ext::pair < typename AutomatonType::StateType, unsigned > > concatenation ( const AutomatonType & first, const AutomatonType & second );
};
 
template < class AutomatonType >
requires isDFA < AutomatonType > || isNFA < AutomatonType >
automaton::NFA < typename AutomatonType::SymbolType, ext::pair < typename AutomatonType::StateType, unsigned > > AutomataConcatenation::concatenation ( const AutomatonType & first, const AutomatonType & second ) {
    static const unsigned NONE = 0;
    static const unsigned FIRST = 1;
    static const unsigned SECOND = 2;
 
    automaton::NFA < typename AutomatonType::SymbolType, ext::pair < typename AutomatonType::StateType, unsigned > > res ( { first.getInitialState ( ), FIRST } );
 
    for ( const auto & q : first.getStates ( ) )
        res.addState ( { q, FIRST } );
    for ( const auto & q : second.getStates ( ) )
        res.addState ( { q, SECOND } );
 
    res.addInputSymbols ( first.getInputAlphabet ( ) );
    res.addInputSymbols ( second.getInputAlphabet ( ) );
 
    for ( const auto & t : first.getTransitions ( ) ) {
        res.addTransition ( { t.first.first, FIRST }, t.first.second, { t.second, FIRST } );
 
        if ( first.getFinalStates ( ).contains ( t.second ) )
            res.addTransition ( { t.first.first, FIRST }, t.first.second, { second.getInitialState ( ), SECOND } );
    }
 
    for ( const auto& t : second.getTransitions ( ) )
        res.addTransition ( { t.first.first, SECOND }, t.first.second, { t.second, SECOND } );
 
    for ( const auto & q : second.getFinalStates ( ) )
        res.addFinalState ( { q, SECOND } );
 
    if ( first.getFinalStates ( ).contains ( first.getInitialState ( ) ) ) {
        ext::pair < typename AutomatonType::StateType, unsigned > q01q02 ( label::InitialStateLabel::instance < typename AutomatonType::StateType > ( ), NONE );
        res.addState ( q01q02 );
        res.setInitialState ( q01q02 );
 
        for ( const auto & t : first.getTransitionsFromState ( first.getInitialState ( ) ) ) {
            res.addTransition ( q01q02, t.first.second, { t.second, FIRST } );
 
            if ( first.getFinalStates ( ).contains ( t.second ) )
                res.addTransition ( q01q02, t.first.second, { second.getInitialState ( ), SECOND } );
        }
 
        for ( const auto & t : second.getTransitionsFromState ( second.getInitialState ( ) ) )
            res.addTransition ( q01q02, t.first.second, { t.second, SECOND } );
 
        if ( second.getFinalStates().contains(second.getInitialState()))
            res.addFinalState ( q01q02 );
    }
 
    return res;
}
 
} /* namespace automaton::transform */