Reduce&Minimize

A.First Edition

This is my third edition of Reduce, which has now ability to minimize DFA first.

B.The problem

I feel unsatisfied with the code. It is ugly! However, I don't have enough energy to make a perfect design.

In order to translate the "Transition Diagram" into "Regular Expression", you need to eliminate all nodes except

the start and final ones. 1. Find out all inward and outward arrows and then replace the node by combining each

inward starting node with each outward ending node. Their expressions should be concatenated.

This edition add a new class Minimize which try to find the equivalent nodes in DFA. I have not got time to write

merge function which should be job for next version.

In the class Minimize, I almost have to extract all five parts of a DFA again: Sigma, Q, Delta, F except S is not

necessary at current stage. The algorithm is just what Dr. Ford described in lecture. I originally try to optimize

the algorithm, then realized that it even add more coding job. So, I retained to original algorithm.

D.The major functions

C.Further improvement

I don't bother to check the result since it is too complicated. So, I have no idea if it is correct or not.

#include <iostream>
#include <fstream>

using namespace std;

const int MaxStateCount=20;
const int MaxSymbolCount = 5;
enum States
{InBound, OutBound, IsLoop};

enum FinalArrow
{StartLoop, StartFinal, FinalStart, FinalLoop};

struct Function
{
	int domain;
	char* expr;
	int range;
	bool isStart;//means the domain is start
	bool isFinal;//means the range is final	
};

class Minimize
{
private:
	Function* pRules;
	char* symbols[MaxSymbolCount];
	int rulesCount;
	int stateCount;
	int symbolCount;
	int rulesTab[MaxStateCount][MaxSymbolCount];
	bool stateTab[MaxStateCount][MaxStateCount];
	int findStr(char* string);
	bool compareState(int i, int j);
	bool isFinal(int state);
public:
	void initialize(Function* inputRules, int rulesSize);
	void doMinimize();
	void display();
};


class Reduce
{
private:
	Minimize min;
	char privateBuffer[512];
	Function rules[30];
	Function temp[30];
	int tempCount;
	int size;
	int inCount;
	int outCount;
	int loopCount;
	//this record the three type arrow(inbound,outbound, loop) for a particular node
	int buffer[3][30];					  	
	bool findStates(int state);
	bool findShortCut(int state);
	void replace(int state);
	void copyFunction(Function* target, Function* source, bool toClear=false);
	void generate();
	void moveRule(int state);
//	bool notAffected(int index);
	void clearState();
	void addFunction(int index);
	void getExpr();
	void copyStr(char* target, const char* source);
	char* getFinalExpr(char str[][256]);
	char* star(const char* source);
	char* dot(char* target, const char* source);
	char* plus(char* target, const char* source);
public:
	void setParam(Function**theRule, int theSize);
	void readRules(const char* fileName);
	void beginReduce();
	void doMinimize();

};

int main()
{
	Reduce R;
	//you need to copy my input file to your local C:
	R.readRules("c:\\newrule.txt");
//	R.beginReduce();
	R.doMinimize();
	
	return 0;
}

bool Minimize::isFinal(int state)
{
	for (int i=0; i<rulesCount; i++)
	{
		if (pRules[i].range==state+1)
		{
			return pRules[i].isFinal;
		}
	}
	return false;
}

void Minimize::display()
{
	for (int i=0; i<stateCount; i++)
	{
		for (int j=0; j<stateCount; j++)
		{
			if (i!=j&&!stateTab[i][j])
			{
				cout<<"("<<i+1<<","<<j+1<<") ";
			}
		}
	}
}


bool Minimize::compareState(int i, int j)
{
	int first, second;
	for (int sym=0; sym<symbolCount; sym++)
	{
		first = rulesTab[i][sym];
		second = rulesTab[j][sym];
	
		if (stateTab[first][second])
		{
			return true;
		}	
	}
	return false;
}


void Minimize::doMinimize()
{
	bool findNew=false;
	do 
	{
		findNew = false;
		for (int i=0; i<stateCount; i++)
		{
			for (int j=0; j<stateCount; j++)
			{
				if (i!=j&&!stateTab[i][j]&&compareState(i, j))
				{
					stateTab[i][j] = true;
					stateTab[j][i] = true;
					findNew=true;
				}

			}
		}
	}
	while (findNew);
}

int Minimize::findStr(char* string)
{
	for (int i=0; i<symbolCount; i++)
	{
		if (strcmp(string, symbols[i])==0)
		{
			return i;
		}
	}
	return -1;
}

void Minimize::initialize(Function* inputRules, int rulesSize)
{
	pRules = inputRules;
	rulesCount = rulesSize;
	stateCount = 0;
	symbolCount =0;
	int symbolIndex;
	//count state, symbols, and translate diagram into matrix
	for (int i=0; i<rulesCount; i++)
	{
		if ((symbolIndex=findStr(pRules[i].expr))<0)
		{
			symbols[i] = new char[strlen(pRules[i].expr)+1];
			strcpy(symbols[i], pRules[i].expr);
			symbolCount++;
		}
		//assume all index of state is continual
		if (pRules[i].domain>stateCount)
		{
			stateCount= pRules[i].domain;
		}
		if (pRules[i].range>stateCount)
		{
			stateCount = pRules[i].range;
		}
		//this is the rules translated into matrix,
		if (symbolIndex<0)
		{
			symbolIndex = symbolCount-1;
		}
		rulesTab[pRules[i].domain-1][symbolIndex] = pRules[i].range-1;	
	}
//	stateCount++;//this is the count
	//write final states as marked, initialize all others to be false
	for (i=0; i<stateCount; i++)
	{
		for (int j=0; j<stateCount; j++)
		{
			stateTab[i][j]=false;
		}
	}
	for (i=0; i<stateCount; i++)
	{
		bool toMark=isFinal(i);
		for (int j=0; j<stateCount; j++)
		{	
			//assume default is false by initialize
			if (i!=j&&toMark)
			{
				stateTab[i][j]= true;
				stateTab[j][i]= true;
			}	
		}
	}
}

char* Reduce::star(const char* source)
{
	if (source==NULL)
	{
		return NULL;
	}
	strcpy(privateBuffer, "star(");
	strcat(strcat(privateBuffer, source), ")");
	return privateBuffer;
}

char* Reduce::dot(char* target, const char* source)
{
	if (source!=NULL)
	{
		if (target==NULL)
		{
			strcpy(target, source);
		}
		else
		{
			strcat(strcat(target, "."), source);
		}
	}
	
	return target;
}

char* Reduce::plus(char* target, const char* source)
{
	if (source==NULL)
	{
		return target;
	}
	strcat(target, "+");
	return strcat(target, source);
}


char* Reduce::getFinalExpr(char str[][256])
{
	//the formula is: star(r1).r2.star(r4+r3.star(r1).r2)
	char exp[512];
	char buf[512];
	strcpy(exp, str[FinalStart]);//r3
	dot(exp, star(str[StartLoop]));
	dot(exp, str[StartFinal]);//r3.star(r1).r2
	dot(exp, str[FinalLoop]); //exp+r4, reversed
	strcpy(buf, star(exp));
	strcpy(exp, str[StartLoop]);//exp=r1
	strcpy(exp, star(exp));//star(r1);
	dot(exp, str[StartFinal]);//exp.r2
	dot(exp, buf);
	strcpy(privateBuffer, exp);
	return privateBuffer;
}


void Reduce::copyStr(char* target, const char* source)
{
//	delete []target;
	target = new char[strlen(source)+1];
	strcpy(target, source);
}

//add a function with index of "index" in rules to "temp"
void Reduce::addFunction(int index)
{
	char str[256];
	//scan to see if there are parallel function already in temp
	for (int i=0; i<tempCount; i++)
	{
		//try to union two expr, if they are parallel
		if (temp[i].domain == rules[index].domain&&temp[i].range==rules[index].range)
		{
			strcpy(str, "(");
			strcat(str, temp[i].expr);
			strcat(strcat(str, "+"), rules[index].expr);
			strcat(str, ")");
			delete []temp[i].expr;
			temp[i].expr = new char[strlen(str)+1];
			strcpy(temp[i].expr, str);
			//tempCount don't increment!
			return;
		}	
	}
	//if not found, copy
	copyFunction(&temp[tempCount], &rules[index]);
	tempCount++;
}

void Reduce::doMinimize()
{
	min.initialize(rules, size);
	min.doMinimize();
	min.display();
}

void Reduce::readRules(const char* fileName)
{
	ifstream f;
	int flag;
	char str[256];
	size = 0;
	f.open(fileName, ios::in);
	while (!f.eof())
	{
		f>>rules[size].domain>>str>>rules[size].range>>flag;
		rules[size].isStart = flag==1?true:false;
		f>>flag;
		rules[size].isFinal = flag==1?true:false;
		rules[size].expr = new char[strlen(str)+1];
		strcpy(rules[size].expr, str);
		size++;
	}
}



void Reduce::clearState()
{
	//those three type arrow should be cleared
	for (int i=0; i<inCount; i++)
	{
		delete [] rules[buffer[InBound][i]].expr;
	}
	for (i=0; i<outCount; i++)
	{
		delete [] rules[buffer[OutBound][i]].expr;
	}
	for (i =0; i<loopCount; i++)
	{
		delete [] rules[buffer[IsLoop][i]].expr;
	}
}

void Reduce::copyFunction(Function* target, Function* source, bool toClear)
{
	target->domain = source->domain;
	target->range = source->range;
	if (toClear)
	{
		delete [] target->expr;
	}
	target->expr = new char[strlen(source->expr)+1];
	strcpy(target->expr, source->expr);
	target->isFinal = source->isFinal;
	target->isStart = source->isStart;
}

void Reduce::moveRule(int state)
{
	for (int i=0; i<size; i++)
	{
		//if not affected
		if (rules[i].domain!=state&&rules[i].range!=state)
		{
			addFunction(i);		
		}
	}
	clearState();
	//copy back from temp to rules, in order for next
	for (i=0; i<tempCount; i++)
	{
		copyFunction(&rules[i], &temp[i]);
	}
	size = tempCount;
}

void Reduce::setParam(Function** theRule, int theSize)
{
	size = theSize;
	for (int i=0; i<size; i++)
	{
		copyFunction(&rules[i], theRule[i]);
	}	
}

void Reduce::replace(int state)
{
	generate();
	moveRule(state);
}

void Reduce::generate()
{
	tempCount=0;
	char str[256];
	int in, out, loop;

	//this handles the trap situation
	if (outCount==0)
	{
		return;
	}
	
	for (int i=0; i<inCount; i++)
	{		
		for (int j=0; j<outCount; j++)
		{
			in = buffer[InBound][i];
			out = buffer[OutBound][j];

			temp[tempCount].domain = rules[in].domain;
			temp[tempCount].isStart = rules[in].isStart;//the start from in
			temp[tempCount].range = rules[out].range;
			temp[tempCount].isFinal = rules[out].isFinal;//final from out
			strcpy(str, rules[in].expr);
			for (int k=0; k<loopCount; k++)
			{
				loop = buffer[IsLoop][k];
				if (k==0)
				{
					strcat(str, ".star");
					strcat(str, "(");
				}
				strcat(strcat(str, rules[loop].expr), "+");
				if (k==loopCount-1)
				{
					//replace '+' with ')'
					str[strlen(str)-1]=')';
				}
			}
			strcat(str, ".");
			strcat(str, rules[out].expr);
			
			temp[tempCount].expr = new char[strlen(str)+1];
			strcpy(temp[tempCount].expr, str);
			//finished one record
			tempCount++;
		}
	}
}


bool Reduce::findStates(int state)
{
	for (int i=0; i<size; i++)
	{		
		if (rules[i].domain==state||rules[i].range==state)
		{
			return true;
		}
	}
	return false;
}

bool Reduce::findShortCut(int state)
{
	inCount = outCount = loopCount = 0;
	for (int i=0; i<size; i++)
	{
		//exclusiveOr and this is a loop
		if (rules[i].domain==state&&rules[i].range==state)
		{
			//the loop 
			if (rules[i].isFinal||rules[i].isStart)
			{
				return false;
			}
			buffer[IsLoop][loopCount]=i;
			loopCount++;
		}
		else
		{			
			if (rules[i].domain==state)
			{
				//if it is start, cannot remove it.
				if (rules[i].isStart)
				{
					return false;
				}
				buffer[OutBound][outCount]=i;
				outCount++;
			}
			if (rules[i].range==state)
			{
				//if it is final, we cannot remove it
				if (rules[i].isFinal)
				{
					return false;
				}			
				buffer[InBound][inCount]=i;
				inCount++;
			}
		}
	}
	//must both have in and out, however, if there is no outBound, it
	//means it is a trap, should be removed immediately
	if (inCount==0)
	{
		cout<<"Error! unaccessable node!\n";
		return false;
	}
	else
	{
		return true;
	}
}
			
void Reduce::getExpr()
{
	char str[4][256];	
	str[0][0]='\0';
	str[1][0]='\0';
	str[2][0]='\0';
	str[3][0]='\0';
	int startLoop =0, startFinal=0, finalStart=0, finalLoop=0, singleLoop=0;
	for (int i=0; i<size; i++)
	{
		//loop at start, not at final
		if (rules[i].isStart&&!rules[i].isFinal&&rules[i].domain==rules[i].range)
		{
			//for the first one, copy "star"
			if (startLoop==0)
			{
				strcat(strcpy(str[StartLoop], "star("), rules[i].expr);
			}
			else
			{
				//for the second or more,
				strcat(str[StartLoop], rules[i].expr);
			}
			strcat(str[StartLoop], "+");
			startLoop++;
		}
		//there is two directions: one from start to final
		//the other is from final to start!!!
		//this is from start to final!
		//I wonder if there is two of such string? should not???
		//yes, it maybe! for an example, there is originally two 
		//parallel arrows between start and final and no operation has
		//ever been taken, so no merge performed.
		if (rules[i].domain!=rules[i].range&&rules[i].isStart&&rules[i].isFinal)
		{
			//the very first expr, use copy
			if (startFinal==0)
			{
				strcpy(str[StartFinal], rules[i].expr);
			}
			else
			{
				//all other use concat
				strcat(str[StartFinal], rules[i].expr);
			}
			strcat(str[StartFinal], "+");
			startFinal++;
		}
		//the arrow from final to start
		if (rules[i].domain!=rules[i].range&&!rules[i].isStart&&!rules[i].isFinal)
		{
			if (finalStart==0)
			{
				strcpy(str[FinalStart], rules[i].expr);
			}
			else
			{
				strcat(str[FinalStart], rules[i].expr);
			}
			strcat(str[FinalStart], "+");
			finalStart++;
		}
		//final loop, but not start loop
		if (rules[i].isFinal&&!rules[i].isStart&&rules[i].domain==rules[i].range)
		{
			//for the first one, copy "star"
			if (finalLoop==0)
			{
				strcat(strcpy(str[FinalLoop], "star("), rules[i].expr);
			}
			else
			{
				//for the second or more,
				strcat(str[FinalLoop], rules[i].expr);
			}
			strcat(str[FinalLoop], "+");
			finalLoop++;
		}
		//here is the spcial case: start and final are the same
		if (rules[i].isFinal&&rules[i].isStart&&rules[i].domain==rules[i].range)
		{
			//for the first one, copy "star"
			if (singleLoop==0)
			{
				//we "borrow" this string to express
				strcat(strcpy(str[StartLoop], "star("), rules[i].expr);
			}
			else
			{
				//for the second or more,
				strcat(str[StartLoop], rules[i].expr);
			}
			strcat(str[StartLoop], "+");
			singleLoop++;
		}
	}
	//overwrite "+" with ")"
	if (singleLoop>0)
	{
		str[StartLoop][strlen(str[StartLoop])-1]=')';
		cout<<str[StartLoop]<<endl;
	}
	else
	{
		if (startLoop>0)
		{
			str[StartLoop][strlen(str[StartLoop])-1]=')';
		}
		if (startFinal>0)
		{
			//must not have more '+'! so write \0 to end
			str[StartFinal][strlen(str[StartFinal])-1]='\0';
		}
		if (finalStart>0)
		{
			str[FinalStart][strlen(str[FinalStart])-1]='\0';
		}
		if (finalLoop>0)
		{
			str[FinalLoop][strlen(str[FinalLoop])-1]=')';
		}
		cout<<getFinalExpr(str)<<endl;
	}
}

void Reduce::beginReduce()
{
	int state=0;
	while (findStates(state))
	{
		if (findShortCut(state))
		{
			replace(state);
		}
		state++;
	}
	getExpr();
}

The result is like following: To see input file, click here.

//the result is like this:
//(1,5) (2,8) (4,6) (5,1) (6,4) (8,2) Press any key to continue

**explanation**

The state number starts from 1 and in continual mode, (I am too lazy to check if there is any number missing.)

This result gives the exact one that Dr. Ford showed in lecture.