ToRegExpAlgebraic.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 <regexp/unbounded/UnboundedRegExp.h>
 
#include <automaton/FSM/DFA.h>
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
#include <automaton/FSM/EpsilonNFA.h>
 
#include <equations/RightRegularEquationSolver.h>
#include <regexp/unbounded/UnboundedRegExpElements.h>
 
namespace automaton {
 
namespace convert {
 
// http://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions
// https://github.com/ferno/greenery/blob/bcc0a136335edbe94cd7725fc6e8cce0268d850c/fsm.py
 
class ToRegExpAlgebraic {
public:
    template < class SymbolType, class StateType >
    static regexp::UnboundedRegExp < SymbolType > convert ( const automaton::EpsilonNFA < SymbolType, StateType > & automaton );
 
    template < class SymbolType, class StateType >
    static regexp::UnboundedRegExp < SymbolType > convert ( const automaton::MultiInitialStateNFA < SymbolType, StateType > & automaton );
 
    template < class T >
    requires isDFA < T > || isNFA < T >
    static regexp::UnboundedRegExp < typename T::SymbolType > convert ( const T & automaton );
};
 
template < class SymbolType, class StateType >
regexp::UnboundedRegExp < SymbolType > ToRegExpAlgebraic::convert ( const automaton::EpsilonNFA < SymbolType, StateType > & automaton ) {
    equations::RightRegularEquationSolver < SymbolType, StateType > solver;
 
    // initialize equations
    solver.setVariableSymbols ( automaton.getStates ( ) );
 
    for ( const StateType & q : automaton.getFinalStates ( ) )
        solver.addEquation ( q, regexp::UnboundedRegExpEpsilon < SymbolType > { } );
 
    for ( const auto & p : automaton.getSymbolTransitions ( ) )
        solver.addEquation ( p.first.first, p.second, regexp::UnboundedRegExpSymbol < SymbolType > { p.first.second } );
 
    for( const auto & p : automaton.getEpsilonTransitions ( ) )
        solver.addEquation ( p.first, p.second, regexp::UnboundedRegExpEpsilon < SymbolType > { } );
 
    return solver.solve ( automaton.getInitialState ( ) );
}
 
template < class SymbolType, class StateType >
regexp::UnboundedRegExp < SymbolType > ToRegExpAlgebraic::convert ( const automaton::MultiInitialStateNFA < SymbolType, StateType > & automaton ) {
    equations::RightRegularEquationSolver < SymbolType, StateType > solver;
 
    // initialize equations
    solver.setVariableSymbols ( automaton.getStates ( ) );
 
    for ( const StateType & q : automaton.getFinalStates ( ) )
        solver.addEquation ( q, regexp::UnboundedRegExpEpsilon < SymbolType > { } );
 
    for ( const auto & p : automaton.getTransitions ( ) )
        solver.addEquation ( p.first.first, p.second, regexp::UnboundedRegExpSymbol < SymbolType > { p.first.second } );
 
    regexp::UnboundedRegExpAlternation < SymbolType > alternation;
    for ( const StateType & initialSymbol : automaton.getInitialStates ( ) )
        alternation.appendElement ( solver.solve ( initialSymbol ).getRegExp ( ).getStructure ( ) ); // set symbol for which the solver will solve equation system
 
    return regexp::UnboundedRegExp < SymbolType > { regexp::UnboundedRegExpStructure < SymbolType > ( alternation ) };
}
 
template < class T >
requires isDFA < T > || isNFA < T >
regexp::UnboundedRegExp < typename T::SymbolType > ToRegExpAlgebraic::convert ( const T & automaton ) {
    using SymbolType = typename T::SymbolType;
    using StateType = typename T::StateType;
 
    equations::RightRegularEquationSolver < SymbolType, StateType > solver;
 
    // initialize equations
    solver.setVariableSymbols ( automaton.getStates ( ) );
 
    for ( const StateType & q : automaton.getFinalStates ( ) )
        solver.addEquation ( q, regexp::UnboundedRegExpEpsilon < SymbolType > { } );
 
    for ( const auto & p : automaton.getTransitions ( ) )
        solver.addEquation ( p.first.first, p.second, regexp::UnboundedRegExpSymbol < SymbolType > { p.first.second } );
 
    return solver.solve ( automaton.getInitialState ( ) );
}
 
} /* namespace convert */
 
} /* namespace automaton */