ToAutomatonDerivation.h

Go to the documentation of this file.

 
#pragma once
 
#include <regexp/formal/FormalRegExp.h>
#include <regexp/unbounded/UnboundedRegExp.h>
 
#include <automaton/FSM/DFA.h>
 
#include <regexp/RegExp.h>
 
#include <alib/set>
#include <alib/deque>
#include <alib/vector>
 
#include <regexp/transform/RegExpDerivation.h>
#include <regexp/simplify/RegExpOptimize.h>
#include <regexp/properties/RegExpEpsilon.h>
 
namespace regexp {
 
namespace convert {
 
class ToAutomatonDerivation {
public:
    template < class T, class SymbolType = typename T::symbol_type >
    static automaton::DFA < SymbolType, unsigned > convert ( const T & regexp );
};
 
template < class T, class SymbolType >
automaton::DFA < SymbolType, unsigned > ToAutomatonDerivation::convert(const T& regexp) {
    // 1.
    T V = regexp::simplify::RegExpOptimize::optimize(regexp);
 
    ext::deque < T > Qi;
 
    Qi.push_back ( V );
 
    ext::map < T, unsigned> stateMap;
    unsigned stateId = 0;
    stateMap.insert ( std::make_pair ( V, stateId ++ ) );
 
    automaton::DFA < SymbolType, unsigned > automaton ( stateMap.at ( V ) );
    automaton.setInputAlphabet(regexp.getAlphabet());
 
    // 2., 3.
    while(! Qi.empty()) {
        T r = std::move ( Qi.back ( ) ); // initialize set Q_i
        Qi.pop_back ( );
 
        for(const auto& a : regexp.getAlphabet()) {
            T derived = regexp::transform::RegExpDerivation::derivation(r, a);
            derived = regexp::simplify::RegExpOptimize::optimize(derived);
 
            // this will also add \emptyset as a regexp (and as FA state)
            if ( ! stateMap.contains ( derived ) ) { // if this state has already been found, do not add
                Qi.push_back(derived);
                automaton.addState ( stateId );
                stateMap.insert ( std::make_pair ( derived, stateId ++ ) );
 
                if(regexp::properties::RegExpEpsilon::languageContainsEpsilon(derived))
                    automaton.addFinalState(stateMap.at(derived));
            }
 
            automaton.addTransition(stateMap.at(r), a, stateMap.at(derived));
        }
    }
 
    if(regexp::properties::RegExpEpsilon::languageContainsEpsilon ( V ) )
        automaton.addFinalState(stateMap.at( V ));
 
    return automaton;
}
 
} /* namespace convert */
 
} /* namespace regexp */