ToRegExpStateElimination.h

/*
 * ToRegExpStateElimination.h
 *
 *  Created on: 9. 2. 2014
 *	  Author: Tomas Pecka
 */

#ifndef TO_REG_EXP_STATE_ELIMINATION_H_
#define TO_REG_EXP_STATE_ELIMINATION_H_

#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 <automaton/FSM/ExtendedNFA.h>

namespace automaton {

namespace convert {

/**
 * Converts FSM to RE using State Elimination algorithm.
 * Source: Melichar 2.118
 */
class ToRegExpStateElimination {
public:
	/**
	 * Performs conversion.
	 * @param automaton automaton to convert
	 * @return regular expression equivalent to source NFA.
	 */
	template<class T>
	static regexp::UnboundedRegExp < > convert(const T& automaton);

private:
	static void extendExtendedNFA(automaton::ExtendedNFA < > & automaton);

	static const regexp::UnboundedRegExpStructure < DefaultSymbolType > transition(const automaton::ExtendedNFA < > & automaton, const DefaultStateType& from, const DefaultStateType& to);

	static automaton::ExtendedNFA < > eliminateState(const automaton::ExtendedNFA < > & extendedAutomaton, const DefaultStateType& state);
};

} /* namespace convert */

} /* namespace automaton */

#endif /* TO_REG_EXP_STATE_ELIMINATION_H_ */