DFA

Reduce with all sequences

    A.Fourth Edition

    This is my fourth edition of Reduce, which has functionality to choose specific elimination sequences.

    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.

C.The idea of program

    This edition add a new menu which get user's input but it is not very useful. The important part of this edition

    is to try all sequences of elimination and see the result. More important, I corrected several bugs in last edition.

    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.

    กก

    //file reduce.h

    #include <iostream>
    #include "menu.h"
    #include <fstream>
    #include "Permutation.h"

    using namespace std;

    const int MaxStateCount=20;
    const int MaxSymbolCount = 5;

    char* menuStr[4]= {"enter the file name of rule",
    			"enter the reduce sequece from keyboard",
    			"enter the reduce sequence from file",
    			"to begin reduce"};
    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:
    	Permutation P;
    	int reduceSeq[MaxStateCount];
    	int stateCount;
    	Minimize min;
    	Menu menu;
    	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);
    	void setSeq(char* sequence);
    	void setSeqFile(const char* fileName);
    public:
    	void getChoice();
    	void getChoice(const char* ruleFileName, const char* sequenceFileName);
    	void setParam(Function**theRule, int theSize);
    	void readRules(const char* fileName);
    	void beginReduce();
    	void doMinimize();
    	void generateAll();
    };

    int main()
    {
    	Reduce R;
    	//you need to copy my input file to your local C:
    	//R.readRules("c:\\newrule.txt");
    //	R.beginReduce();
    	//R.doMinimize();
    //	R.getChoice("c:\\examrules.txt", "c:\\seq.txt");
    	//the result is like this:
    	//(1,5) (2,8) (4,6) (5,1) (6,4) (8,2) Press any key to continue
    	R.generateAll();

    	return 0;
    }

    void Reduce::generateAll()
    {
    	readRules("c:\\examrules.txt");
    	P.setFileName("c:\\seq.txt");
    	P.setSize(stateCount);
    	P.generate();
    	setSeqFile("c:\\seq.txt");

    }

    void Reduce::setSeqFile(const char* fileName)
    {
    	ifstream in;
    	char buffer[256];
    	int index=0;
    	in.open(fileName, ios::in);
    	while (!in.eof())
    	{
    		if (index==stateCount)
    		{
    			beginReduce();
    			index=0;
    		}
    		else
    		{
    			in>>buffer;
    			reduceSeq[index]=atoi(buffer);
    			index++;
    		}
    	}
    	if (index==stateCount)
    	{
    		beginReduce();
    	}
    }

    void Reduce::getChoice(const char* ruleFileName, const char* sequenceFileName)
    {
    	ifstream in;
    	char buffer[256];
    	int index=0;
    	readRules(ruleFileName);
    	in.open(sequenceFileName, ios::in);
    	while (!in.eof())
    	{
    		if (index==stateCount)
    		{
    			beginReduce();
    			index=0;
    		}
    		else
    		{
    			in>>buffer;
    			reduceSeq[index]=atoi(buffer);
    			index++;
    		}
    	}
    	if (index==stateCount)
    	{
    		beginReduce();
    	}
    	//setSeq(buffer);

    }

    void Reduce::setSeq(char* sequence)
    {
    	char* ptr= sequence;
    	int index=0;
    	if (sequence!=NULL)
    	{
    		for (int i=0;i<stateCount; i++)
    		{
    			if ((ptr=strtok(ptr, " \n"))!=NULL)
    			{
    				reduceSeq[i]=atoi(ptr);
    			}
    			else
    			{
    				cout<<"some sequence not readable\n";
    				reduceSeq[i]=0;
    			}
    			ptr=NULL;
    		}
    	}
    	else
    	{
    		for (int i=0; i<stateCount; i++)
    		{
    			reduceSeq[i]=i;
    		}
    	}
    }

    void Reduce::getChoice()
    {
    	int index=0;
    	ifstream f;
    	char sequence[256];
    	char buffer[256];
    	bool userSeq=false;
    	bool ruleSet=false;
    	char** temp=&menuStr[0];
    	menu.setMenu(temp, 4);

    	while (true)
    	{
    		index=menu.input(false);
    		switch (index)
    		{
    		case 0:
    			cout<<"please enter the file name for the rules\n";
    			cin>>buffer;
    			readRules(buffer);
    			ruleSet=true;
    			break;
    		case 1:
    			cout<<"please enter the reduce sequence by index of states"
    				<<"(the first state is indexed as 0)\n";
    			cin>>sequence;
    			userSeq=true;
    			break;
    		case 2:
    			cout<<"please enter the file name of reduce sequence\n";
    			cin>>buffer;
    			f.open(buffer, ios::in);
    			f>>sequence;
    			userSeq = true;
    			break;
    		case 3:
    			if (!ruleSet)
    			{
    				cout<<"you haven't set up rules!\n";
    				break;
    			}
    			cout<<"now begin reduce...\n";
    			if (userSeq)
    			{
    				setSeq(sequence);
    			}
    			else
    			{
    				setSeq(NULL);
    			}
    			//doMinimize();
    			beginReduce();
    			return;
    		}
    	}
    }

    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 (strcmp(source, "")==0)
    	{
    		return "";
    	}
    	strcpy(privateBuffer, "star(");
    	strcat(strcat(privateBuffer, source), ")");
    	return privateBuffer;
    }

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

    	return target;
    }

    char* Reduce::plus(char* target, const char* source)
    {
    	if (strcmp(source, "")!=0)
    	{
    		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]={'\0'};
    	char buf[512]={'\0'};
    	//if r3 not exists, no need at all
    	if (strcmp("", str[FinalStart])!=0)
    	{
    		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;
    	stateCount=0;
    	f.open(fileName, ios::in);
    	while (!f.eof())
    	{
    		f>>rules[size].domain>>str>>rules[size].range>>flag;
    		if (rules[size].domain>=stateCount)//make stateCount the biggest
    		{
    			stateCount=rules[size].domain;
    		}
    		if (rules[size].range>=stateCount)//make stateCount the biggest
    		{
    			stateCount=rules[size].range;
    		}
    		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++;
    	}
    	stateCount++;//cause it is the count,
    }

    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,and change the ')' to '+'
    				str[StartLoop][strlen(str[StartLoop])-1]='+';
    				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], "(");
    				strcat(str[StartFinal], rules[i].expr);
    			}
    			else
    			{
    				//all other use concat, change the last ')' to +
    				str[StartFinal][strlen(str[StartFinal])-1]='+';
    				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], "(");
    				strcpy(str[FinalStart], rules[i].expr);
    			}
    			else
    			{
    				str[FinalStart][strlen(str[FinalStart])-1]='+';
    				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,
    				str[StartLoop][strlen(str[StartLoop])-1]='+';
    				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;
    	for (int i=0; i<stateCount; i++)
    	{
    		state = reduceSeq[i];
    		if (findStates(state))
    		{
    			if (findShortCut(state))
    			{
    				replace(state);
    			}
    		}
    	}
    	getExpr();
    }

    //file name is menu.h

    //a helper class for inputting

    /*********************************************************
    *Name of file: menu.h
    *function: It is a generic class for input menus.
    *Idea of program: Whatever an input menu is simply ask user to
    *	input a number to indicate his choice which has some associated
    *	infomation displayed. So I just set up a menu by inputing a
    *	set of strings and return the number which user input.
    *	I also want it to have a set of automatical response by
    *	inputing a set of function pointers which can be called when a
    *	number is entered.
    ************************************************************/
    #include <iostream>

    using namespace std;

    const int MaxMenuItems = 10;
    const int MaxTitleLength = 60;
    class Menu
    {
    private:
    	char titles[MaxMenuItems][MaxTitleLength];
    	void (*respondList[MaxMenuItems])();
    	int itemCount;
    	int quitIndex;
    	int getInput();
    	void printMenu();
    public:
    	void setMenu(char** menuTitles, int titleNum);
    	int input(bool useDefault=true);
    	void setRespond(int index, void (*respond)());
    	void setQuitIndex(int index);//this is not very useful
    };

    void Menu::setQuitIndex(int index)
    {
    	if (index<itemCount)
    	{
    		quitIndex = index;
    	}
    	else
    	{
    		cout<<"Out of menu count!\n";
    	}
    }

    void Menu::setMenu(char** menuTitles, int titleNum)
    {
    	itemCount = titleNum;
    	for (int i=0; i< titleNum; i++)
    	{
    		strcpy(titles[i], menuTitles[i]);
    		respondList[i]=NULL;
    	}
    	quitIndex = itemCount-1;//by default it should quit at last item
    }

    void Menu::setRespond(int index, void (*respond)())
    {
    	if (index<itemCount)
    	{
    		respondList[index] = respond;
    	}
    	else
    	{
    		cout<<"Out of menu count!\n";
    	}
    }

    int Menu::input(bool useDefault)
    {
    	int index;
    	index = getInput();
    	if (useDefault)
    	{
    		if (respondList[index]!=NULL)
    		{
    			respondList[index];
    		}
    	}
    	return index;
    }

    void Menu::printMenu()
    {
    	cout<<"\n       Menu (choose by enter item index)\n";
    	for (int i=0; i<itemCount; i++)
    	{
    		cout<<"\t("<<i+1<<") "<<titles[i]<<endl;
    	}
    	cout<<"choice>";
    }

    int Menu::getInput()
    {
    	//char buffer[20];
    	int result=0;
    	printMenu();
    	do
    	{
    		cin>>result;
    		if (result<1||result>itemCount)
    		{
    			cout<<"Please enter a number for your choices!\n";
    		}
    	}
    	while (result<1||result>itemCount);
    	return result-1;
    }

    //file name permutation.h

    //a helper class to generate all permutations

    #include <iostream>
    #include <fstream>

    using namespace std;

    const int MaxLength=20;
    const char* outputFileName="c:\\seq.txt";
    class Permutation
    {
    private:
    	int lst[MaxLength];
    	int size;
    	ofstream out;
    	void output();
    	void perm(int* array, int length, int index);
    	void swap(int* array, int i, int j);
    	void initialize();
    public:
    	Permutation(const char* outputName= outputFileName, int newSize=6);
    	void setSize(int newSize);
    	void setFileName(const char* outputName);
    	void generate(){perm(lst, size, 0);}
    };

    void Permutation::output()
    {
    	for (int i=0; i<size; i++)
    	{
    		out<<"  "<<lst[i];
    	}
    	out<<"\n";
    }

    void Permutation::setFileName(const char* outputName)
    {
    	out.open(outputName, ios::out);
    }

    void Permutation::setSize(int newSize)
    {
    	size=newSize;
    	initialize();
    }

    void Permutation::initialize()
    {
    	for (int i=0; i<size; i++)
    	{
    		lst[i]=i;
    	}
    }

    Permutation::Permutation(const char*outputName, int newSize)
    {
    	size = newSize;
    	out.open(outputName);
    	initialize();
    	perm(lst, size, 0);
    }

    void Permutation::swap(int *array, int i, int j)
    {
    	int temp=array[i];
    	array[i]=array[j];
    	array[j]= temp;
    }

    void Permutation::perm(int* array, int length, int index)
    {
    	if (length>1)
    	{
    		for (int i=1; i<length; i++)
    		{
    			swap(array, 0, i);
    			perm(array+1, length-1, i-1);
    			swap(array, 0, i);
    		}
    	}
    	output();
    }

    The result is like following:

    //the result is like this:
    star(a.a.a).((((a+b).b+(a.a+a.b)).b+a.a.b))
    star(a.a.a).((((a+b).b+(a.a+a.b)).b+a.a.b))
    star(a.a.a).((((a+b).b+(a.a+a.b)).b+a.a.b))
    star(a.a.a).((((a+b).b+(a.a+a.b)).b+a.a.b))
    star(a.a.a).((((a+b).b+(a.a+a.b)).b+a.a.b))

    ...

    กก

    //this is examrules.txt

    0 a 1 1 0
    0 a 3 1 0
    0 b 3 1 0
    1 a 2 0 0
    1 a 4 0 0
    1 b 4 0 0
    2 a 0 0 0
    2 b 5 0 1
    3 b 4 0 0
    4 b 5 0 1

    //this is all sequence generated by Permutation class in file "seq.txt"

    1 2 3 4 5 0
    1 2 3 4 0 5
    1 2 3 5 0 4
    1 2 3 5 4 0
    1 2 3 0 4 5
    1 2 4 0 5 3
    1 2 4 0 3 5
    1 2 4 5 3 0
    1 2 4 5 0 3
    1 2 4 3 0 5
    1 2 5 4 0 3
    1 2 5 4 3 0
    1 2 5 0 3 4
    1 2 5 0 4 3
    1 2 5 3 4 0
    1 2 0 3 4 5
    1 3 0 4 5 2
    1 3 0 4 2 5
    1 3 0 5 2 4
    1 3 0 5 4 2
    1 3 0 2 4 5
    1 3 4 2 5 0
    1 3 4 2 0 5
    1 3 4 5 0 2
    1 3 4 5 2 0
    1 3 4 0 2 5
    1 3 5 4 2 0
    1 3 5 4 0 2
    1 3 5 2 0 4
    1 3 5 2 4 0
    1 3 5 0 4 2
    1 3 2 0 4 5
    1 4 3 0 5 2
    1 4 3 0 2 5
    1 4 3 5 2 0
    1 4 3 5 0 2
    1 4 3 2 0 5
    1 4 0 2 5 3
    1 4 0 2 3 5
    1 4 0 5 3 2
    1 4 0 5 2 3
    1 4 0 3 2 5
    1 4 5 0 2 3
    1 4 5 0 3 2
    1 4 5 2 3 0
    1 4 5 2 0 3
    1 4 5 3 0 2
    1 4 2 3 0 5
    1 5 3 4 0 2
    1 5 3 4 2 0
    1 5 3 0 2 4
    1 5 3 0 4 2
    1 5 3 2 4 0
    1 5 4 2 0 3
    1 5 4 2 3 0
    1 5 4 0 3 2
    1 5 4 0 2 3
    1 5 4 3 2 0
    1 5 0 4 2 3
    1 5 0 4 3 2
    1 5 0 2 3 4
    1 5 0 2 4 3
    1 5 0 3 4 2
    1 5 2 3 4 0
    1 0 2 3 4 5
    2 0 3 4 5 1
    2 0 3 4 1 5
    2 0 3 5 1 4
    2 0 3 5 4 1
    2 0 3 1 4 5
    2 0 4 1 5 3
    2 0 4 1 3 5
    2 0 4 5 3 1
    2 0 4 5 1 3
    2 0 4 3 1 5
    2 0 5 4 1 3
    2 0 5 4 3 1
    2 0 5 1 3 4
    2 0 5 1 4 3
    2 0 5 3 4 1
    2 0 1 3 4 5
    2 3 1 4 5 0
    2 3 1 4 0 5
    2 3 1 5 0 4
    2 3 1 5 4 0
    2 3 1 0 4 5
    2 3 4 0 5 1
    2 3 4 0 1 5
    2 3 4 5 1 0
    2 3 4 5 0 1
    2 3 4 1 0 5
    2 3 5 4 0 1
    2 3 5 4 1 0
    2 3 5 0 1 4
    2 3 5 0 4 1
    2 3 5 1 4 0
    2 3 0 1 4 5
    2 4 3 1 5 0
    2 4 3 1 0 5
    2 4 3 5 0 1
    2 4 3 5 1 0
    2 4 3 0 1 5
    2 4 1 0 5 3
    2 4 1 0 3 5
    2 4 1 5 3 0
    2 4 1 5 0 3
    2 4 1 3 0 5
    2 4 5 1 0 3
    2 4 5 1 3 0
    2 4 5 0 3 1
    2 4 5 0 1 3
    2 4 5 3 1 0
    2 4 0 3 1 5
    2 5 3 4 1 0
    2 5 3 4 0 1
    2 5 3 1 0 4
    2 5 3 1 4 0
    2 5 3 0 4 1
    2 5 4 0 1 3
    2 5 4 0 3 1
    2 5 4 1 3 0
    2 5 4 1 0 3
    2 5 4 3 0 1
    2 5 1 4 0 3
    2 5 1 4 3 0
    2 5 1 0 3 4
    2 5 1 0 4 3
    2 5 1 3 4 0
    2 5 0 3 4 1
    2 1 0 3 4 5
    3 2 0 4 5 1
    3 2 0 4 1 5
    3 2 0 5 1 4
    3 2 0 5 4 1
    3 2 0 1 4 5
    3 2 4 1 5 0
    3 2 4 1 0 5
    3 2 4 5 0 1
    3 2 4 5 1 0
    3 2 4 0 1 5
    3 2 5 4 1 0
    3 2 5 4 0 1
    3 2 5 1 0 4
    3 2 5 1 4 0
    3 2 5 0 4 1
    3 2 1 0 4 5
    3 0 1 4 5 2
    3 0 1 4 2 5
    3 0 1 5 2 4
    3 0 1 5 4 2
    3 0 1 2 4 5
    3 0 4 2 5 1
    3 0 4 2 1 5
    3 0 4 5 1 2
    3 0 4 5 2 1
    3 0 4 1 2 5
    3 0 5 4 2 1
    3 0 5 4 1 2
    3 0 5 2 1 4
    3 0 5 2 4 1
    3 0 5 1 4 2
    3 0 2 1 4 5
    3 4 0 1 5 2
    3 4 0 1 2 5
    3 4 0 5 2 1
    3 4 0 5 1 2
    3 4 0 2 1 5
    3 4 1 2 5 0
    3 4 1 2 0 5
    3 4 1 5 0 2
    3 4 1 5 2 0
    3 4 1 0 2 5
    3 4 5 1 2 0
    3 4 5 1 0 2
    3 4 5 2 0 1
    3 4 5 2 1 0
    3 4 5 0 1 2
    3 4 2 0 1 5
    3 5 0 4 1 2
    3 5 0 4 2 1
    3 5 0 1 2 4
    3 5 0 1 4 2
    3 5 0 2 4 1
    3 5 4 2 1 0
    3 5 4 2 0 1
    3 5 4 1 0 2
    3 5 4 1 2 0
    3 5 4 0 2 1
    3 5 1 4 2 0
    3 5 1 4 0 2
    3 5 1 2 0 4
    3 5 1 2 4 0
    3 5 1 0 4 2
    3 5 2 0 4 1
    3 1 2 0 4 5
    4 2 3 0 5 1
    4 2 3 0 1 5
    4 2 3 5 1 0
    4 2 3 5 0 1
    4 2 3 1 0 5
    4 2 0 1 5 3
    4 2 0 1 3 5
    4 2 0 5 3 1
    4 2 0 5 1 3
    4 2 0 3 1 5
    4 2 5 0 1 3
    4 2 5 0 3 1
    4 2 5 1 3 0
    4 2 5 1 0 3
    4 2 5 3 0 1
    4 2 1 3 0 5
    4 3 1 0 5 2
    4 3 1 0 2 5
    4 3 1 5 2 0
    4 3 1 5 0 2
    4 3 1 2 0 5
    4 3 0 2 5 1
    4 3 0 2 1 5
    4 3 0 5 1 2
    4 3 0 5 2 1
    4 3 0 1 2 5
    4 3 5 0 2 1
    4 3 5 0 1 2
    4 3 5 2 1 0
    4 3 5 2 0 1
    4 3 5 1 0 2
    4 3 2 1 0 5
    4 0 3 1 5 2
    4 0 3 1 2 5
    4 0 3 5 2 1
    4 0 3 5 1 2
    4 0 3 2 1 5
    4 0 1 2 5 3
    4 0 1 2 3 5
    4 0 1 5 3 2
    4 0 1 5 2 3
    4 0 1 3 2 5
    4 0 5 1 2 3
    4 0 5 1 3 2
    4 0 5 2 3 1
    4 0 5 2 1 3
    4 0 5 3 1 2
    4 0 2 3 1 5
    4 5 3 0 1 2
    4 5 3 0 2 1
    4 5 3 1 2 0
    4 5 3 1 0 2
    4 5 3 2 0 1
    4 5 0 2 1 3
    4 5 0 2 3 1
    4 5 0 1 3 2
    4 5 0 1 2 3
    4 5 0 3 2 1
    4 5 1 0 2 3
    4 5 1 0 3 2
    4 5 1 2 3 0
    4 5 1 2 0 3
    4 5 1 3 0 2
    4 5 2 3 0 1
    4 1 2 3 0 5
    5 2 3 4 0 1
    5 2 3 4 1 0
    5 2 3 0 1 4
    5 2 3 0 4 1
    5 2 3 1 4 0
    5 2 4 1 0 3
    5 2 4 1 3 0
    5 2 4 0 3 1
    5 2 4 0 1 3
    5 2 4 3 1 0
    5 2 0 4 1 3
    5 2 0 4 3 1
    5 2 0 1 3 4
    5 2 0 1 4 3
    5 2 0 3 4 1
    5 2 1 3 4 0
    5 3 1 4 0 2
    5 3 1 4 2 0
    5 3 1 0 2 4
    5 3 1 0 4 2
    5 3 1 2 4 0
    5 3 4 2 0 1
    5 3 4 2 1 0
    5 3 4 0 1 2
    5 3 4 0 2 1
    5 3 4 1 2 0
    5 3 0 4 2 1
    5 3 0 4 1 2
    5 3 0 2 1 4
    5 3 0 2 4 1
    5 3 0 1 4 2
    5 3 2 1 4 0
    5 4 3 1 0 2
    5 4 3 1 2 0
    5 4 3 0 2 1
    5 4 3 0 1 2
    5 4 3 2 1 0
    5 4 1 2 0 3
    5 4 1 2 3 0
    5 4 1 0 3 2
    5 4 1 0 2 3
    5 4 1 3 2 0
    5 4 0 1 2 3
    5 4 0 1 3 2
    5 4 0 2 3 1
    5 4 0 2 1 3
    5 4 0 3 1 2
    5 4 2 3 1 0
    5 0 3 4 1 2
    5 0 3 4 2 1
    5 0 3 1 2 4
    5 0 3 1 4 2
    5 0 3 2 4 1
    5 0 4 2 1 3
    5 0 4 2 3 1
    5 0 4 1 3 2
    5 0 4 1 2 3
    5 0 4 3 2 1
    5 0 1 4 2 3
    5 0 1 4 3 2
    5 0 1 2 3 4
    5 0 1 2 4 3
    5 0 1 3 4 2
    5 0 2 3 4 1
    5 1 2 3 4 0
    0 1 2 3 4 5

กก

**explanation**

I used all sequences to eliminate the NFA and the result is unexpectedly same which surprised me a lot!!!

    กก