nfa-to-dfa.cpp

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

	#endif
	}
	
	for(;;)
	{
		bool flag=false;
		
		for(int i=0; i<n; i++)
		{
			vector<int> &transitions=states[i].transitions;
			if(reachable_from_initial[i])
			{
				for(int j=0; j<number_of_symbols; j++)
					if(transitions[j]!=-1 && !reachable_from_initial[transitions[j]])
					{
					#ifdef DFA_THOROUGHLY_DEBUG_DEAD_STATES
						cout << i << " is reachable from initial ==> " << transitions[j] << " also is.\n";
					#endif
						reachable_from_initial[transitions[j]]=true;
						flag=true;
					}
			}
			if(!can_lead_to_final[i])
			{
				for(int j=0; j<number_of_symbols; j++)
					if(transitions[j]!=-1 && can_lead_to_final[transitions[j]])
					{
					#ifdef DFA_THOROUGHLY_DEBUG_DEAD_STATES
						cout << transitions[j] << " can lead to final ==> " << i << " also can.\n";
					#endif
						can_lead_to_final[i]=true;
						flag=true;
						break;
					}
			}
		}
		
		if(!flag) break;
	}
	
	for(int i=0; i<n; i++)
		state_is_live.push_back(reachable_from_initial[i] && can_lead_to_final[i]);
	
#ifdef DFA_DEBUG_DEAD_STATES
	for(int i=0; i<n; i++)
		if(!state_is_live[i])
		{
			cout << "state " << i << " is dead because it ";
			if(!reachable_from_initial[i])
				cout << "is unreachable from initial state";
			if(!reachable_from_initial[i] && !can_lead_to_final[i])
				cout << " and ";
			if(!can_lead_to_final[i])
				cout << "cannot lead to a final state";
			cout << ".\n";
		}
#endif
}

// partition.state_to_group[i]==j means that state i belongs to state group j.
// i \in partition.groups[j] means the same.
// if partition.state_to_group[i]==-1, then state i belongs to no state group
// and is ignored. In this case for all j not(i \in partition_groups[j]).
// partition.size() returns number of subsets in partition.
// minimize_dfa() takes an initial partition from partition.state_to_group
// (partition.groups is ignored) and completes the job of dividing the set of
// states into classes of equivalence.
// The function returns the number of those classes.
// If something is wrong with the source data, -1 is returned.
int minimize_dfa(DFA &dfa, DFA::Partition &partition)
{
#ifdef DEBUG_DFA_MINIMIZATION
	cout << "minimize_dfa(): arrived here.\n";
#endif
	if(!partition.state_to_group.size())
	{
		// if no initial partition is supplied, we shall divide the
		// states into accepting, nonaccepting and dead.
		dfa.determine_dead_states();
		for(int i=0; i<dfa.states.size(); i++)
			if(!dfa.state_is_live[i])
				partition.state_to_group.push_back(-1);
			else if(dfa.states[i].is_accepting)
				partition.state_to_group.push_back(1);
			else
				partition.state_to_group.push_back(0);
	}
	if(partition.state_to_group.size()!=dfa.states.size()) return -1;
	
#ifdef DEBUG_DFA_MINIMIZATION
	cout << "checkpoint 1\n";
#endif
	
	for(int i=0; i<dfa.states.size(); i++)
		if(partition.state_to_group[i]!=-1)
		{
			while(partition.state_to_group[i]>=partition.groups.size())
				partition.groups.push_back(set<int>());
			partition.groups[partition.state_to_group[i]].insert(i);
		}
	
#ifdef DEBUG_DFA_MINIMIZATION
	cout << "checkpoint 2\n";
#endif
	
	partition.group_to_original_group.clear();
	for(int i=0; i<partition.groups.size(); i++)
		partition.group_to_original_group.push_back(i);
	
#ifdef DEBUG_DFA_MINIMIZATION
	cout << "checkpoint 3\n";
#endif
	
	for(;;)
	{
		bool repeat_from_the_beginning=false;
		
		// note: vector partition.groups shall grow.
		for(int i=0; i<partition.groups.size(); i++)
		{
		#ifdef DEBUG_DFA_MINIMIZATION
			cout << i << ": " << partition.groups[i] << "\n";
		#endif
			if(partition.groups[i].size()<=1) continue;
			
			for(;;)
			{
				set<int> &group=partition.groups[i];
				bool repeat_flag=false;
				
				// trying to split this group
				for(int j=0; j<dfa.number_of_symbols; j++)
				{
					// all states in this group should have transitions
					// on j to states in target_group.
					int target_state=dfa.states[*group.begin()].transitions[j];
					int target_group_number=(target_state!=-1 ? partition.state_to_group[target_state] : -1);
					int new_target_group_number=-1;
					
					set<int>::iterator p;
					bool split_flag=false;
					for(p=group.begin(); p!=group.end(); p++)
					{
						int this_target_state=dfa.states[*p].transitions[j];
						new_target_group_number=(this_target_state!=-1 ? partition.state_to_group[this_target_state] : -1);
						if(new_target_group_number!=target_group_number)
						{
						#ifdef DEBUG_DFA_MINIMIZATION
							cout << "symbol " << j << ": target group is " << new_target_group_number << " (" << target_group_number << " expected).\n";
						#endif
							split_flag=true;
							break;
						}
					}
					
					if(!split_flag) continue;
					
					// splitting.
					set<int> new_group;
					int new_group_number=partition.groups.size();
					for(; p!=group.end(); p++)
					{
						int this_target_state=dfa.states[*p].transitions[j];
						int this_target_group=(this_target_state!=-1 ? partition.state_to_group[this_target_state] : -1);
						if(this_target_group==new_target_group_number)
							new_group.insert(*p);
					}
					for(set<int>::iterator p2=new_group.begin(); p2!=new_group.end(); p2++)
					{
						group.erase(*p2);
						partition.state_to_group[*p2]=new_group_number;
					}
					
					partition.groups.push_back(new_group);
					partition.group_to_original_group.push_back(partition.group_to_original_group[i]);
//					assert(partition.groups.size()==partition.group_to_original_group.size());
					
					repeat_flag=true;
				#ifdef DEBUG_DFA_MINIMIZATION
					cout << "setting repeat flag.\n";
				#endif
					break;
				}
				
				if(!repeat_flag) break;
			#ifdef DEBUG_DFA_MINIMIZATION
				cout << "repeat\n";
				cout << i << ": " << partition.groups[i] << "\n";
			#endif
				repeat_from_the_beginning=true;
			}
		}
		if(!repeat_from_the_beginning) break;
	#ifdef DEBUG_DFA_MINIMIZATION
		cout << "repeat from the beginning\n";
	#endif
	}
	
	partition.group_containing_initial_state=partition.state_to_group[0];
	
#ifdef DEBUG_DFA_MINIMIZATION
	cout << "minimize_dfa(): about to return.\n";
#endif
	return partition.groups.size();
}

void NFA::print(ostream &os)
{
	for(int i=0; i<states.size(); i++)
	{
		State &state=states[i];
	#if 0
		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.
	#endif
		os << "State " << i;
		if(state.is_accepting)
			os << " (Accepting)";
		else if(state.is_important)
			os << " (Important)";
		os << ": ";
		
		bool written_smth=false;
		if(state.transitions.size())
		{
			os << "transitions " << state.transitions;
			written_smth=true;
		}
		if(state.epsilon_transitions.size())
		{
			if(written_smth) os << "; ";
			os << "epsilon transitions to " << state.epsilon_transitions;
			written_smth=true;
		}
		if(!written_smth)
			os << "No outgoing transitions";
		os << ".\n";
	}
}

void DFA::raw_print(ostream &os)
{
	for(int i=0; i<states.size(); i++)
	{
		State &state=states[i];
		
		os << i;
		if(state.is_accepting) os << "(Acc)";
		os << "\t";
		os << state.transitions << "\n";
	}
}
void DFA::print(ostream &os)
{
	for(int i=0; i<states.size(); i++)
	{
		State &state=states[i];
		
		os << "State " << i;
		if(state.is_accepting)
			os << " (Accepting)";
		
		if(state.nfa_states.size())
			os << " (NFA states " << state.nfa_states << ")";
		
		std::map<int, vector<int> > target_states;
		for(int j=0; j<state.transitions.size(); j++)
			if(state.transitions[j]>=0)
				target_states[state.transitions[j]].push_back(j);
		
		if(target_states.size()==0)
			os << ": No outgoing transitions.\n";
		else
		{
			os << ": ";
			
			for(std::map<int, vector<int> >::iterator p=target_states.begin(); p!=target_states.end(); p++)
			{
				if(p!=target_states.begin())
					os << ", ";
				
				if(p->second.size()==1)
					os << p->second[0];
				else
					os << p->second;
				
				os << " -> " << p->first;
			}
			os << "\n";
		}
	}
}	

char *character_to_string(int c)
{
	static char buffer[20];
	if(c=='\n')
		return "LF";
	else if(c=='\r')
		return "CR";
	else if(c=='\t')
		return "Tab";
	else if(c==' ')
		return "Space";
	else if(c=='"')
		return "\\\x22";
	else if(c=='\\')
		return "\\\\";
	else if(c>' ' && c<128)
	{
		sprintf(buffer, "%c", c);
		return buffer;
	}
	else
	{
		sprintf(buffer, "0x%02x", c);
		return buffer;
	}
}

void print_transitions_from_one_state_in_dot_format(int from, std::map<int, vector<int> > target_states, ostream &os)
{
	for(map<int, vector<int> >::iterator p=target_states.begin(); p!=target_states.end(); p++)
	{
		const vector<int> &v=p->second;
		
		os << "\tState" << from << " -> " << "State" << p->first << " [label=\x22";
		
		for(int pointer=0; pointer<v.size(); )
		{
			if(pointer>0) os << ",";
			int end_of_region=pointer;
			while(end_of_region+1<v.size() && v[end_of_region+1]-v[end_of_region]==1)
				end_of_region++;
			
			if(end_of_region==pointer)
				os << character_to_string(v[pointer]);
			else
			{
				os << character_to_string(v[pointer]);
				os << "..";
				os << character_to_string(v[end_of_region]);
			}
			
			pointer=end_of_region+1;
		}
		os << "\x22];\n";
	}
}

void DFA::print_in_dot_format(ostream &os)
{
	os << "\n";
	os << "/* A DFA created by Dolphin. */\n";
	os << "\ndigraph G\n";
	os << "{\n";
	os << "\tcenter=true;\n";
	os << "\trankdir=LR;\n";
	
	for(int i=0; i<states.size(); i++)
	{
		os << "\tState" << i << " [label=\x22" << i << "\x22";
		if(states[i].is_accepting)
			os << ", shape=doublecircle";
		else
			os << ", shape=circle";
		os << "];\n";
	}
	for(int i=0; i<states.size(); i++)
	{
		State &state=states[i];
		
		map<int, vector<int> > target_states;
		for(int j=0; j<state.transitions.size(); j++)
			if(state.transitions[j]>=0)
				target_states[state.transitions[j]].push_back(j);
		print_transitions_from_one_state_in_dot_format(i, target_states, os);
	}
	os << "}\n";
}	

void NFA::print_in_dot_format(ostream &os)
{
	os << "digraph G\n";
	os << "{\n";
	os << "\tcenter=true;\n";
	os << "\trankdir=LR;\n";
	
	for(int i=0; i<states.size(); i++)
	{
		os << "\tState" << i << " [label=\x22" << i << "\x22";
		if(states[i].is_accepting)
			os << ", shape=doublecircle";
		else
			os << ", shape=circle";
		if(states[i].is_important)
			os << ", style=filled";
		os << "];\n";
	}
	for(int i=0; i<states.size(); i++)
	{
		State &state=states[i];
		
		map<int, vector<int> > target_states;
		for(int j=0; j<state.transitions.size(); j++)
			target_states[state.transitions[j].second].push_back(state.transitions[j].first);
		print_transitions_from_one_state_in_dot_format(i, target_states, os);
		for(int j=0; j<state.epsilon_transitions.size(); j++)
			os << "\tState" << i << " -> State" << state.epsilon_transitions[j] << " [fontname=\x22Symbol\x22, label=\x22" "e" "\x22];\n";
	}
	os << "}\n";
}