Brzozowski.cpp

/*
 * Brzozowski.cpp
 *
 *  Created on: 11. 1. 2014
 *      Author: tomas
 */

#include "Brzozowski.h"

using namespace std;
using namespace alib;
using namespace automaton;
using namespace regexp;

namespace conversions
{

Brzozowski::Brzozowski( const RegExp & re ) : m_re( re )
{

}

Brzozowski::~Brzozowski( void )
{

}

FSM Brzozowski::convert( void )
{
    RegExpOptimize opt;

    // 1.
    RegExp V = opt.optimize( m_re );
    set<alphabet::Symbol> alphabet = m_re.getAlphabet( );

    set<RegExp> Q = { V };
    deque<set<RegExp>> Qi;

    Qi.push_back( set<RegExp>( ) );
    Qi.at( 0 ).insert( V );

    int i = 1;

    // 2.
    while( ! Qi.at( i - 1 ).empty( ) )
    {
        Qi.push_back( set<RegExp>( ) ); // initialize set Q_i

        for( const auto & regexp : Qi.at( i - 1 ) )
        {
            RegExpDerivation deriv( regexp );

            for( const auto & a : alphabet )
            {
                RegExp derived = deriv.derivation( a );
                derived = opt.optimize( derived );

                // this will also add \emptyset as a regexp (and as FA state)
                if( ! isInSet( derived, Q ) ) // if this state has already been found, do not add
                    Qi.at( i ).insert( derived );

            }
        }

        Q.insert( Qi.at( i ).begin( ), Qi.at( i ).end( ) );

        i += 1;
    }

    // ------------------------------------------------------------------------
    // 3.

    FSM automaton;
    int stateId = 0;
    map<RegExp, State> stateMap;

    for( const auto & r : Q )
    {
        State q( toBase26( stateId ++ ) );
        stateMap.insert( std::pair<RegExp,State>( r, q ) );
        automaton.addState( q );
    }

    for( const auto & a : alphabet )
        automaton.addInputSymbol( a.getSymbol( ) );

    for( const auto & r : Q )
    {
        RegExpDerivation deriv( r );

        for( const auto & a: automaton.getInputAlphabet( ) )
        {
            RegExp derived = deriv.derivation( a );
            derived = opt.optimize( derived );

            TransitionFSM t( stateMap.find( r )->second, a, stateMap.find( derived )->second );
            if( ! isInSet( t, automaton.getTransitions( ) ) )
                automaton.addTransition( t );
        }
    }

    automaton.addInitialState( stateMap.find( V )->second );

    for( const auto & U : Q )
        if( U.containsEmptyString( ) )
            automaton.addFinalState( stateMap.find( U )->second );

    return automaton;
}

} /* namespace conversions */