DeterminizeNFAPart.hxx

/*
 * NFADeterminizer.cpp
 *
 *  Created on: 16. 1. 2014
 *	  Author: Jan Vesely
 */

#include "common/NFACommon.h"

#include <automaton/FSM/NFA.h>
#include <automaton/FSM/MultiInitialStateNFA.h>
#include <alib/deque>
#include <alib/algorithm>
#include <alib/set>

namespace automaton {

namespace determinize {

template < class SymbolType, class StateType >
automaton::DFA < SymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::MultiInitialStateNFA < SymbolType, StateType > & nfa ) {
	 // 1, 4
	ext::set < StateType > initialState = nfa.getInitialStates ( );
	automaton::DFA < SymbolType, ext::set < StateType > > res ( initialState );

	res.setInputAlphabet ( nfa.getInputAlphabet ( ) );

	 // 2
	ext::deque < ext::set < StateType > > todo;
	todo.push_back ( std::move ( initialState ) );

	do {
		 // 3a, c
		ext::set < StateType > state = std::move ( todo.front ( ) );
		todo.pop_front ( );

		 // 3b
		for ( const SymbolType & input : nfa.getInputAlphabet ( ) ) {
			ext::set < StateType > dfaState;

			for ( StateType nfaState : state ) {
				auto iter = nfa.getTransitions ( ).find ( ext::make_pair ( std::move ( nfaState ), input ) );

				if ( iter != nfa.getTransitions ( ).end ( ) )
					dfaState.insert ( iter->second.begin ( ), iter->second.end ( ) );
			}

			 // 4
			bool existed = !res.addState ( dfaState );

			if ( !existed ) todo.push_back ( dfaState );

			 // 3b
			res.addTransition ( state, input, std::move ( dfaState ) );
		}
	} while ( !todo.empty ( ) );

	 // 5
	const ext::set < StateType > & finalLabels = nfa.getFinalStates();
	for ( const ext::set < StateType > & dfaState : res.getStates ( ) )
		if ( ! ext::excludes ( finalLabels.begin ( ), finalLabels.end ( ), dfaState.begin ( ), dfaState.end ( ) ) )
			res.addFinalState ( dfaState );

	return res;
}

template < class SymbolType, class StateType >
automaton::DFA < SymbolType, ext::set < StateType > > Determinize::determinize ( const automaton::NFA < SymbolType, StateType > & nfa ) {
	 // 1, 4
	ext::set < StateType > initialState;
	initialState.insert ( nfa.getInitialState ( ) );
	automaton::DFA < SymbolType, ext::set < StateType > > res ( initialState );

	res.setInputAlphabet ( nfa.getInputAlphabet ( ) );

	 // 2
	ext::deque < ext::set < StateType > > todo;
	todo.push_back ( std::move ( initialState ) );

	do {
		 // 3a, c
		ext::set < StateType > state = std::move ( todo.front ( ) );
		todo.pop_front ( );

		 // 3b
		for ( const SymbolType & input : nfa.getInputAlphabet ( ) ) {
			ext::set < StateType > dfaState;

			for ( StateType nfaState : state ) {
				auto iter = nfa.getTransitions ( ).find ( ext::make_pair ( std::move ( nfaState ), input ) );

				if ( iter != nfa.getTransitions ( ).end ( ) )
					dfaState.insert ( iter->second.begin ( ), iter->second.end ( ) );
			}

			 // 4
			bool existed = !res.addState ( dfaState );

			if ( !existed ) todo.push_back ( dfaState );

			 // 3b
			res.addTransition ( state, input, std::move ( dfaState ) );
		}
	} while ( !todo.empty ( ) );

	 // 5
	const ext::set < StateType > & finalLabels = nfa.getFinalStates();
	for ( const ext::set < StateType > & dfaState : res.getStates ( ) )
		if ( ! ext::excludes ( finalLabels.begin ( ), finalLabels.end ( ), dfaState.begin ( ), dfaState.end ( ) ) )
			res.addFinalState ( dfaState );

	return res;
}

} /* namespace determinize */

} /* namespace automaton */