Minimal DFA.cpp computes minimal DFA by partition factoring.

dfaMinimizer.cpp

/*
	This is computationally terrible and resource abusive...
	I just did this to finish some homework for me.
*/

#include <iostream>
#include "dfaMinimizer.hpp"
#include <vector>
#include <map>


//#define DEBUG
#define SET vector<State>
#define MULTISET vector<vector<State> >

using namespace std;

bool samePartition( MULTISET, int, int );
bool sameSet( SET, int, int );
void removeExcess( SET& );
SET  regroup( MULTISET& );
void reduce( MULTISET& );

int main(int argc, char const *argv[])
{

	/* create the table */
	SET s = exampleTable();
	/* remove states that aren't the start state and nothing transitions to */
	removeExcess( s );
	cout << "\n\nWithout impossible producers" << endl;
	print("\n\tUSED\ta\tb", s);


	/* split into accept, and not accept states */
	SET Accept = acceptStates( s );
	SET Normal = normalStates( s );
	cout << "\n\nInitial partition" << endl;
	print("\n\tAccpt\ta\tb", Accept);
	print("\n\tNorml\ta\tb", Normal);

	/* put those into a multiset */
	MULTISET master;
	master.push_back(Accept);
	master.push_back(Normal);

	reduce( master );

	cout << "\n\nReduced partitions" << endl;
	for (int i = 0; i < master.size(); ++i)
		print("",master[i]);
	
	SET final = regroup( master );
	print("\tFINAL",final);

	cout << endl << endl;
	return 0;
		
}

void reduce( MULTISET &v ) {
	/* for each partition 'i' in 'v' */
	for (int i = 0; i < v.size(); ++i) {
		if( v[i].size() < 3 ) continue;
		/* compare each element 'j' of 'i' */
		for (int j = 0; j < v[i].size(); ++j) {
			/* with each element of that same partition 'i' */
			for (int y = j; y < v[i].size(); ++y) {
				if( v[i][j] == v[i][y] ) continue;
				/* to see if they both transition in the same way */
				bool okay = true;
				for (int c = 0; c < SIZE_OF_ALPHABET && okay; ++c) {
					/* with edges that end in the same partition */
					int v1 = v[i][j].On( Alphabet[c] );
					int v2 = v[i][y].On( Alphabet[c] );
                                        /* and identical vertices are clearly in the same partition */
					if( v1 == v2 ) continue;
					#ifdef DEBUG
						cout << "is " << v1 << "," << v2 << " in the same partition?" << endl;
					#endif
                                        /* but when they're not identical their edges must end with vertices of the same partition */
					if( !samePartition( v, v1, v2 ) ) okay = false;
				}
				if( okay ) {
					/* if all transitions from the vertices satisfy the above, create a new partition with those two */
					SET v2;
					v2.push_back( v[i][j] );
					v2.push_back( v[i][y] );
					#ifdef DEBUG
						for (int k = 0; k < v.size(); ++k)
							print("B",v[k]);
						cout << "REMOVE " << v[i][j] << endl;
						cout << "REMOVE " << v[i][y] << endl;
					#endif
                                        /* and remove them from the original partition */
					v[i].erase( v[i].begin() + j );					
					v[i].erase( v[i].begin() + y-1 );
                                        /* then put that new partition into the multiset */
					v.push_back( v2 );				
					#ifdef DEBUG
						for (int k = 0; k < v.size(); ++k)
							print("A",v[k]);
					#endif
                                        /* and repeat until there is no change NOTE! this example doesn't handle this condition perfectly */
					reduce( v );
					return;
				}				
			}
		}
	}
}

bool samePartition( MULTISET v, int a, int b ) {
	int size = v.size();
	for (int i = 0; i < size; ++i)
		if( sameSet(v[i], a, b) ) return true;
	return false;
}

bool sameSet( SET v, int a, int b ) {
	int found = 0;
	for (int i = 0; i < v.size() && found < 2; ++i)
		if( v[i].vertex == a || v[i].vertex == b )
			found++;
	return found == 2;
}

SET regroup( MULTISET &v ) {
	typedef map<int, int> pairwise;
	pairwise pair;
	SET completed;
	int id = 1;
	cout << endl;

	/* initialize ID map */
	for (int i = 0; i < v.size(); ++i, ++id) {
		for (int j = 0; j < v[i].size(); ++j) {
			if( pair.find( v[i][j].vertex ) == pair.end() ){
				pair[ v[i][j].vertex ] = id;
				#ifdef DEBUG
					cout << "\tMap(" << v[i][j].vertex  << ',' << id << ")\n";
				#endif
			}
		}
	}
	cout << endl;

	for (int i = 0; i < v.size(); ++i) {
		completed.push_back( State(false) );
		/* assign ID */
		id = pair[ v[i].back().vertex ];
		completed.back().edges = new Transition[SIZE_OF_ALPHABET];

		/* for each symbol */
		for( int c = 0; c < SIZE_OF_ALPHABET; ++c ) {
			char on = Alphabet[c];
			bool unset = true;
			/* check each state */
			for (int j = 0; j < v[i].size(); ++j) {
				/* combine the types of each into one */
				if( v[i][j].Accept ) completed.back().Accept = true;
				if( v[i][j].Start  ) completed.back().Start  = true;	

				/* find the first successful transition */
				int  to = v[i][j].On( on );
				if( to == 0 ) continue;
				unset = false;
				completed.back().Set( id, c, pair[to] );
			}
			/* if there is no proper transition, allow it to move to state 0*/
			if( unset )
				completed.back().Set( id, c, 0x0 );
		}
	}	

	return completed;
}

void removeExcess( SET& v ) {
	for (int i = 0; i < v.size(); ++i) {
		if( v[i].Start ) continue;
		int  vert = v[i].vertex;
		bool okay = false;
		for (int j = 0; j < v.size(); ++j) {
			for (int c = 0; c < SIZE_OF_ALPHABET && !okay; ++c) {
				if( v[j].On( Alphabet[c] ) == vert ) {
					okay = true;
					break;
				}	
			}
		}
		if( !okay ) {
			v.erase( v.begin() + i );
		}
	}

}

dfaMinimizer.hpp

#define SIZE_OF_ALPHABET 2

#include <iostream>
#include <vector>
using namespace std;
const char Alphabet[SIZE_OF_ALPHABET] = {'a','b'};
const size_t table_size = 8;




class Transition {
public:
	char on;
	int  to;
	Transition() {}
	void Set(char o, int t) {
		this->on = o;
		this->to = t;
	}
};

class State {
public:
	int vertex, i;
	bool skip, Accept, Start;
	Transition * edges;

	State(){
		this->i = 0;
		this->skip = this->Accept = this->Start = false;
		this->edges = new Transition[SIZE_OF_ALPHABET];
	}
	State(bool f) {
		this->i = 0;
		this->skip = this->Accept = this->Start = false;		
	}
	void Set(int id, char c, int i){
		this->vertex = id;
		this->edges[this->i] = Transition();
		this->edges[this->i].Set(c,i);
		this->i++;
	}
	void Set(int id, int c, int i){
		this->vertex = id;
		this->edges[c].Set(c,i);
	}
	int On( char c ) {
		for (int i = 0; i < this->i; ++i)
			if(this->edges[i].on == c)
				return this->edges[i].to;
		return 0;
	}
	std::string type() {
		std::string text = "  ";
		text[0] = this->Accept? '*' : ' ';
		text[1] = this->Start? '>' : ' ';
		return text;	
	}
	bool operator == (const State &ref) const 
	{
		if( this->vertex == ref.vertex ) return true;
		//for (int i = 0; i < SIZE_OF_ALPHABET; ++i)
		//	if(this->edges[i].to != ref.edges[i].to) return false;
		return false;
	}

	friend std::ostream& operator<< (std::ostream& out, const State& s) {
		out << s.vertex << '\t';	
		for (int i = 0; i < SIZE_OF_ALPHABET; ++i)
			if( s.edges[i].to != 0 )
				out << s.edges[i].to << '\t';
			else
				out << "-\t";
		return out;
	}
};

void print(string s, vector<State> v ) {
	cout << s << endl;
	for (int i = 0; i < v.size(); ++i)
		cout << '\t' << v[i].type() << v[i] << endl;
}

vector<State> acceptStates( vector<State> s) {
	vector<State> v;
	for (int i = 0; i < s.size(); ++i)
		if( s[i].Accept )
			v.push_back(s[i]);
	return v;
}
vector<State> normalStates( vector<State> s) {
	vector<State> v;
	for (int i = 0; i < s.size(); ++i)
		if( !s[i].Accept )
			v.push_back(s[i]);
	return v;
}

/*
	start with a list of vertex, edges so a table like 	
	STATE	a	b
	>1		2	4
	*2		4	7
	 3		5	-
	 4		8	-
	*5		4	3
	 6		5	4
	 7		2	-
	 8		2	4
	looks like the below, NOTE - is 0
*/
vector<State> exampleTable() {
	vector<State>  s;
	s.push_back(State());
	s.back().Start = true;
	s.back().Set(1,'a',2);
	s.back().Set(1,'b',4);
	s.push_back(State());
	s.back().Set(2,'a',4);
	s.back().Set(2,'b',7);
	s.back().Accept = true;
	s.push_back(State());
	s.back().Set(3,'a',5);
	s.back().Set(3,'b',0);
	s.push_back(State());
	s.back().Set(4,'a',8);
	s.back().Set(4,'b',0);
	s.push_back(State());
	s.back().Set(5,'a',4);
	s.back().Set(5,'b',3);
	s.back().Accept = true;
	s.push_back(State());
	s.back().Set(6,'a',5);
	s.back().Set(6,'b',4);
	s.push_back(State());
	s.back().Set(7,'a',2);
	s.back().Set(7,'b',0);
	s.push_back(State());
	s.back().Set(8,'a',2);
	s.back().Set(8,'b',4);
	return s;
}