DeterminizeNFAPart.cxx

/*
 * 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 <deque>
#include <algorithm>

namespace automaton {

namespace determinize {

automaton::DFA Determinize::determinize(const automaton::MultiInitialStateNFA& nfa) {
	// 1, 4
	automaton::State initialState(createDFAState(nfa.getInitialStates()));
	automaton::DFA res(initialState);
	res.setInputSymbols(nfa.getInputAlphabet());
	
	// 2
	std::deque<automaton::State> todo;
	todo.push_back(initialState);
	
	do {
		// 3a, c
		automaton::State state = todo.front();
		todo.pop_front();

		// 3b
		for (const auto& input : nfa.getInputAlphabet()) {
			std::set<automaton::State> targetNFAStates;
			for(const auto& nfaState : recreateNFAStates(state)) {
				auto iter = nfa.getTransitions().find(std::make_pair(nfaState, input));
				if(iter != nfa.getTransitions().end()) {
					targetNFAStates.insert(iter->second.begin(), iter->second.end());
				}
			}
			automaton::State dfaState = createDFAState(targetNFAStates);

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

			// 3b
			res.addTransition(state, input, dfaState);

			if(!existed) todo.push_back(dfaState);
		}
	} while(!todo.empty());
	
	// 5
	for (const auto& dfaState : res.getStates()) {
		std::set<automaton::State> nfaStates = recreateNFAStates(dfaState);
		if(std::any_of(nfaStates.begin(), nfaStates.end(), [&](const automaton::State& nfaState) { return nfa.getFinalStates().count(nfaState); })) {
			res.addFinalState(dfaState);
		}
	}
	
	return res;
}

automaton::DFA Determinize::determinize(const automaton::NFA& nfa) {
	// 1, 4
	automaton::State initialState(createDFAState({nfa.getInitialState()}));
	automaton::DFA res(initialState);
	res.setInputSymbols(nfa.getInputAlphabet());
	
	// 2
	std::deque<automaton::State> todo;
	todo.push_back(initialState);
	
	do {
		// 3a, c
		automaton::State state = todo.front();
		todo.pop_front();

		// 3b
		for (const auto& input : nfa.getInputAlphabet()) {
			std::set<automaton::State> targetNFAStates;
			for(const auto& nfaState : recreateNFAStates(state)) {
				auto iter = nfa.getTransitions().find(std::make_pair(nfaState, input));
				if(iter != nfa.getTransitions().end()) {
					targetNFAStates.insert(iter->second.begin(), iter->second.end());
				}
			}
			automaton::State dfaState = createDFAState(targetNFAStates);

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

			// 3b
			res.addTransition(state, input, dfaState);

			if(!existed) todo.push_back(dfaState);
		}
	} while(!todo.empty());
	
	// 5
	for (const auto& dfaState : res.getStates()) {
		std::set<automaton::State> nfaStates = recreateNFAStates(dfaState);
		if(std::any_of(nfaStates.begin(), nfaStates.end(), [&](const automaton::State& nfaState) { return nfa.getFinalStates().count(nfaState); })) {
			res.addFinalState(dfaState);
		}
	}
	
	return res;
}

} /* namespace determinize */

} /* namespace automaton */