nfa-to-dfa.h

Full support for extended regular expressions (those with intersection and complement); Support for

// NFA to DFA conversion library.
// (C) Alexander Okhotin <[e-mail]>, 1999-2002.
// (C) Vladimir Prus <[e-mail]>, 2000.

#ifndef __DOLPHIN__NFA_TO_DFA_H

#define __DOLPHIN__NFA_TO_DFA_H

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <stdexcept>

#define NUMBER_OF_TRANSITIONS_TO_STORE_IN_LINEAR_MEMORY 2

//#define DEBUG_NFA
//#define DEBUG_NFA_DESTRUCTOR
//#define DEBUG_DFA
//#define NFA_TO_DFA_THROW_EXCEPTIONS

class DFA
{
	void state_should_exist(int n)
	{
		while(states.size()<=n)
			states.push_back(State());
	}
	
public:
	struct State
	{
		std::vector<int> nfa_states;
		std::vector<int> transitions;
		bool is_accepting;
		
		State() : is_accepting(false) {}
		
		void add_transition(int target, int symbol)
		{
			while(transitions.size()<=symbol)
				transitions.push_back(-1);
			transitions[symbol]=target;
		}
	};
	
	struct Partition
	{
		std::vector<int> state_to_group;
		std::vector<std::set<int> > groups;
		std::vector<int> group_to_original_group;
		int group_containing_initial_state;
	};
	
	std::vector<State> states;
	int number_of_symbols;
	
	std::vector<bool> state_is_live;
	
	int add_state()
	{
		int n=states.size();
		states.push_back(State());
		return n;
	}
	void add_transition(int from, int to, int symbol)
	{
		states[from].add_transition(to, symbol);
	#ifdef DEBUG_DFA
		std::cout << "DFA: Adding transition from " << from << " to " << to << " upon " << symbol << "\n";
	#endif
	}
//	Partition make_initial_partition();
	void align_transition_table();
	void raw_print(std::ostream &os);
	void print(std::ostream &os);
	void print_in_dot_format(std::ostream &os);
	void determine_dead_states();
	int incorporate_dfa(const DFA &dfa)
	{
		int offset=states.size();
		for(int i=0; i<dfa.states.size(); i++)
		{
			const State &s=dfa.states[i];
			for(int j=0; j<s.transitions.size(); j++)
			{
				state_should_exist(i+offset);
				if(s.transitions[j]>=0)
					state_should_exist(s.transitions[j]+offset);
				add_transition(i+offset, s.transitions[j]+offset, j);
			}
			states[offset+i].is_accepting=s.is_accepting;
		}
		return offset;
	}
};

class NFA
{
	void state_should_exist(int n)
	{
		while(states.size()<=n)
			states.push_back(State(number_of_symbols));
	}
	
public:
	/** Initial size of epsilon_transitions array */
	static const int def_epsilon_transitions=16;

	struct State
	{
		std::vector<std::pair<int, int> > transitions;

		std::vector<int> epsilon_transitions;
		
		bool is_accepting;
		bool is_important; // see Aho/Sethi/Ullman 1986, p. 134.
		
		State(int number_of_symbols) :
			epsilon_transitions(def_epsilon_transitions),
			is_accepting(false), is_important(false)
		{ epsilon_transitions.clear(); }
		
		void add_transition(int target, int symbol)
		{
			is_important=true;
			transitions.push_back(std::make_pair(symbol, target));
		}
		void add_epsilon_transition(int target)
		{
			epsilon_transitions.push_back(target);
		}
	};
	
	std::vector<State> states;
	int number_of_symbols;
	
	NFA(int supplied_number_of_symbols)
	{
		number_of_symbols=supplied_number_of_symbols;
	}

	void add_transition(int from, int to, int symbol)
	{
		state_should_exist(from);
		state_should_exist(to);
	#ifdef NFA_TO_DFA_THROW_EXCEPTIONS
		if(symbol>=number_of_symbols)
			throw std::logic_error("NFA::add_transition(): Symbol number out of range");
	#endif
		states[from].add_transition(to, symbol);
	#ifdef DEBUG_NFA
		std::cout << "NFA: Adding transition from " << from << " to " << to << " upon " << symbol << "\n";
	#endif
	}
	void add_epsilon_transition(int from, int to)
	{
		state_should_exist(from);
		state_should_exist(to);
		states[from].add_epsilon_transition(to);
	#ifdef DEBUG_NFA
		std::cout << "NFA: Adding transition from " << from << " to " << to << " upon epsilon\n";
	#endif
	}
	void mark_as_accepting(int n)
	{
		state_should_exist(n);
		states[n].is_accepting=true;
		states[n].is_important=true;
	}
	// returns offset, i.e. the number N, such that the state i of the given nfa
	// is mapped onto the state N+i of the host nfa.
	int incorporate_nfa(const NFA &nfa)
	{
		int offset=states.size();
		for(int i=0; i<nfa.states.size(); i++)
		{
			const State &s=nfa.states[i];
			for(int j=0; j<s.transitions.size(); j++)
				add_transition(i+offset, s.transitions[j].second+offset, s.transitions[j].first);
			for(int j=0; j<s.epsilon_transitions.size(); j++)
				add_epsilon_transition(i+offset, s.epsilon_transitions[j]+offset);
			states[offset+i].is_accepting=s.is_accepting;
			states[offset+i].is_important=s.is_important;
		}
		return offset;
	}
	void mark_as_important(int n)
	{
		state_should_exist(n);
		states[n].is_important=true;
	}
	int add_state()
	{
		int n=states.size();
		states.push_back(State(number_of_symbols));
		return n;
	}
	void raw_print(std::ostream &os);
	void print(std::ostream &os);
	void print_in_dot_format(std::ostream &os);
};


void epsilon_closure(NFA &nfa);
void convert_nfa_to_dfa(NFA &nfa, DFA &dfa);
int minimize_dfa(DFA &dfa, DFA::Partition &partition);

#undef DEBUG_NFA
#undef DEBUG_DFA

#endif