DFA

A.First Edition

This is my first edition of DFA, however you can also regard it as a recursive edition of DFS. I am quite satisfied

with this edition as its clearance of logic and simplicity of algorithm and data structure are much more superior 

than all previous editions. 

B.The problem

1. You need to generate a series of numbers.

2. The first number is either 12 or 13.

3. The length of sequence is four numbers.

4. The order of sequence is determined by following rules:

5. If the sequence starts with a 12, then the last (fourth) number is either 21, 31 or 32. Otherwise, if the

sequence starts with a 13, then the last (fourth) number is either 31 or 32.

6. You are asked to generate all possible sequences. 

I feel no happy, even disappointed for my DFS class! I didn't expect it had such a big bug after so many times 

improvement! It shame me a lot! My logical for fixed level search is not clear, so I didn't realize that I need to 

stop the program when it reaches the bottom by all means. 

After all the assignment's simple recursive algorithm really attracts me a lot. As long as efficiency is not my

consideration, why don't I try recursive to simplify my program which is by now too complicated.

Also DFA's idea impressed me so much that I even admire myself since I am so lucky to use idea of DFA to solve

so many problems all by myself. Because I never realize that DFS=DFA until I listen to lecture of comp335.

A Depth-First-Search is by all means able to implement by recursive call as recursive call will always execute the

very bottom one where they stop. I am still afraid to write the complicated pointer manipulating code of DFS. 

With recursive call, everything is OK except efficiency. But should I worry too much about efficiency?

I also save a lot of memory by remove those meaningless class objects list from my DFA class. In DFS user only 

check the path he got, should he care about the sibling nodes? I guess not. 

In DFA all choices are simply an element from Sigama, do we really need to care about the exact symbol? No, only

the index of symbol in Sigama matters. So, I only use a simple array to store the index choices chosen by user.

Why should I spend so much time to create a tree of objects of DFS? It is meaningless! OOP only want to combine 

method with particular data structure, why should I create those useless nodes? So, now in memory there is simply 

one object created, counted. That's it!

D.The major functions

E.Further improvement

F.File list

1. file: DFA.h

2. file: DFA.cpp

3. file: sequence.cpp (main)

//file: DFA.h

///////////////////////////////////////////////////////
//file: DFA.h-------the header file of DFA class
//author: Qingzhe Huang
//date: Sep. 26, 2003
//class name: DFA---Deterministic Finite Automaton
//Purpose:
//	1. This class is a general searching class and it has
//	an another name: DFA---Depth-First-Search.
//	For all searching problem, we simply can store all possible choices
//	into a choice list, and for each possible state, use a loop to test
//	each choice. If return true, we can generate a new node, if not, test
//	next. Before this assignment, I write all DFS by generating a tree of class
//	nodes, but it simply too complicated. Now that efficiency is not the most
//	important issue. I use recursive to simplify all pointer manipulations.
//
//	2. This class is an abstract base class, all derived class need to implement
//	two basic function: 
//		a) checkSymbol: this gives the transition rule
//		b) evaluate: this gives the success condition of searching
/////////////////////////////////////////////////////////////////////////////


#ifndef DFA_H
#define DFA_H

//I arbitrarily decide that the search level won't be more than 100 levels
const int MaxSearchLevel= 100;

class DFA
{
protected:
	int count;
	int symbolCount;
	int maxLevel;
	char** symbolStr;
	int level;//is count, level 0 stores nothing!
	bool findAll;
	bool countOnly;
	int path[MaxSearchLevel];
	void generate();
	void update(int sonData);
	void restore(int sonData);
	bool touchDown();
	virtual void output();
	virtual void doUpdate(int sonData);
	virtual void doRestore(int sonData);	
	//derived class must overload these functions!
	virtual	bool evaluate()=0;
	virtual bool checkSymbol(int sonData)=0;
public:
	//size of sigma must be defined, if user has his own label string, must 
	//pass the string array pointer here, otherwise only output default index
	void setParam(int symbolSize, int maxSearchLevel=20, char** symbolString=NULL, 
		bool findAllChoices=false, bool onlyCount=false);
	int getCount() const { return count;}
	void search();//simply call generate()
	DFA(): count(0){;}
};
#endif

//file: DFA.cpp

/////////////////////////////////////////////////////////////
//file: DFA.cpp
//This is the implementation of class DFA
////////////////////////////////////////////////////////////

#include <iostream>
#include "DFA.H"

using namespace std;

//////////////////////////////////////////////////////////////////////////
//This function must be called before call search to begin searching
//as it will initialize all parameter of class
//Parameter:
//	a)symbolSize: is the size of array of choices
//	b)maxSearchLevel: is the max search level set by user, searching will
//		stop whenever encounter this level limit.
//	c)symbolString: is optional. It will display an array of user-defined
//		strings when output
//	d)findAllChoices: will not stop when find first target when set to be true
//	e)onlyCount: will not output if set to be true
//////////////////////////////////////////////////////////////////////		
void DFA::setParam(int symbolSize, int maxSearchLevel, char** symbolString, 
				   bool findAllChoices, bool onlyCount)
{
	symbolCount = symbolSize;
	maxLevel = maxSearchLevel;
	symbolStr = symbolString;
	findAll = findAllChoices;
	countOnly = onlyCount;
	level = 0;
	count = 0;
}

void DFA::search()
{
	generate();
}

////////////////////////////////////////////////////////////////
//if user pass a string array pointer by "setParam" function, it 
//will display result according to that array, otherwise it will 
//simply display index of choices
////////////////////////////////////////////////////////////////
void DFA::output()
{
	cout<<"Solution No."<<count<<" is:\n";
	if (symbolStr==NULL)
	{		
		for (int i=0; i<level; i++)
		{
			cout<<path[i]<<'\t';
		}	
	}
	else
	{
		for (int i=0; i<level; i++)
		{
			cout<<symbolStr[path[i]]<<'\t';
		}
	}
	cout<<endl;
}

///////////////////////////////////////////////////////////////
//This is the major function which will recursively call itself to
//make the DFS search automatically.
//It uses a loop to check each choice to see if new node can be generated.
//If true, update itself, recursively call generate.
//It will stop generating when it reaches max Searching level which is setup
//by user at "setParam" function.
//////////////////////////////////////////////////////////////////////////
void DFA::generate()
{
	if (level!=0)
	{
		//check before test bottom
		if (evaluate())
		{
			count++;
			if (!countOnly)
			{
				output();
			}
			
			//only want one solution
			if (!findAll)
			{
				return;
			}			
		}
	}
	//always check to ensure!
	if (touchDown())
	{
		return;
	}

	for (int i=0; i< symbolCount; i++)
	{
		if (checkSymbol(i))
		{
			update(i);
			generate();
			restore(i);
		}
	}
}

////////////////////////////////////////////////////////////////////////
//user may want to do some extra updating job, so I leave that choice in
//function "doUpdate" which is a virtual function to be overrided.
//////////////////////////////////////////////////////////////////////
void DFA::update(int sonData)
{
	level++;
	path[level-1] = sonData;
	doUpdate(sonData);
}

//////////////////////////////////////////////////////////////////////
//similarly if user wants extra job for "restoring", a virtual function
//"doRestore" can be overloaded.
/////////////////////////////////////////////////////////////////////
void DFA::restore(int sonData)
{
	level--;
	doRestore(sonData);
}

////////////////////////////////////////////////////////////////////////
//This function prevents inifinitely deep search in some cases when solution
//is easy to be found in other shallow nodes. Because it stops generating
//more nodes when this max searching level met.
//////////////////////////////////////////////////////////////////////////
bool DFA::touchDown()
{
	return level==maxLevel;
}


void DFA::doRestore(int sonData)
{
	//leave for user's choices!
}

void DFA::doUpdate(int sonData)
{
	//leave for user's choices!
}



//file: sequence.cpp

///////////////////////////////////////////////////////////////////////
//file: sequence.cpp
//This is derived class called "Sequence" to inherite from "DFA" to generate
//all sequences of length 4 and counts all number of sequences when length
//increases to 6 without printing out sequences.
//////////////////////////////////////////////////////////////////////////
#include <iostream>
#include "DFA.H"

using namespace std;

//This is the choice array to be passed by "setParam" function
int numbers[6] = {12, 13, 21, 23, 31, 32};
char* numberStr[6]={"12", "13", "21", "23", "31", "32"};

//this 
class Sequence: public DFA
{
protected:
	virtual bool checkSymbol(int sonData);
	virtual bool evaluate();
};


int main()
{
	Sequence Seq;
	//this means: 6 symbol, max level 4, user-defined string array "numberStr"
	//need to find all sequences, output all result
	Seq.setParam(6, 4, numberStr, true);
	Seq.search();
	//this means: 6 symbol, max level 6, no user-defined display strings
	//find all suitable choices, don't display result
	Seq.setParam(6, 6, NULL, true, true);
	Seq.search();
	cout<<"For length 6 the total number of solution is:"<<Seq.getCount()<<endl;
	
	return 0;
}

/////////////////////////////////////////////////////////////////////////////
//different searching problem certainly has different success conditions.
//In this case, when length or level is 4
/////////////////////////////////////////////////////////////////////////
bool Sequence::evaluate()
{
	return level== maxLevel;
}

//////////////////////////////////////////////////////////////////////////////
//this is simply a translation of the rules.
//Pls note that at the last position, it should be decided by both the last number
//and the first number, so it is an "And"
///////////////////////////////////////////////////////////////////////////////
bool Sequence::checkSymbol(int sonData)
{
	bool result = false;
	int current;  
	int selected = numbers[sonData];
	int first;
	if (level==0)
	{
		return selected ==12||selected == 13;
	}
	
	current = numbers[path[level-1]];
	switch (current)
	{
	case 12:
		result = selected==12||selected==13||selected==23||selected==21;
		break;
	case 13:
		result = selected==13||selected==23||selected==21||selected==31;
		break;
	case 23:
		result = selected==23||selected==21||selected==31||selected==32;
		break;
	case 21:
		result = selected==21||selected==31||selected==32;
		break;
	case 31:
		result = selected==31||selected==32;
		break;
	case 32:
		result = selected==32;
		break;
	}
	if (level+1<maxLevel)
	{
		return result;
	}
	else
	{
		first = numbers[path[0]];
		switch (first)
		{
		case 12:
			result = result &&(selected==21||selected==31||selected==32);
			break;
		case 13:
			result = result &&(selected==31||selected==32);
			break;
		}
		return result;
	}

}

The result is like following:

Solution No.1 is:
12 12 12 21
Solution No.2 is:
12 12 13 21
Solution No.3 is:
12 12 13 31
Solution No.4 is:
12 12 21 21
Solution No.5 is:
12 12 21 31
Solution No.6 is:
12 12 21 32
Solution No.7 is:
12 12 23 21
Solution No.8 is:
12 12 23 31
Solution No.9 is:
12 12 23 32
Solution No.10 is:
12 13 13 21
Solution No.11 is:
12 13 13 31
Solution No.12 is:
12 13 21 21
Solution No.13 is:
12 13 21 31
Solution No.14 is:
12 13 21 32
Solution No.15 is:
12 13 23 21
Solution No.16 is:
12 13 23 31
Solution No.17 is:
12 13 23 32
Solution No.18 is:
12 13 31 31
Solution No.19 is:
12 13 31 32
Solution No.20 is:
12 21 21 21
Solution No.21 is:
12 21 21 31
Solution No.22 is:
12 21 21 32
Solution No.23 is:
12 21 31 31
Solution No.24 is:
12 21 31 32
Solution No.25 is:
12 21 32 32
Solution No.26 is:
12 23 21 21
Solution No.27 is:
12 23 21 31
Solution No.28 is:
12 23 21 32
Solution No.29 is:
12 23 23 21
Solution No.30 is:
12 23 23 31
Solution No.31 is:
12 23 23 32
Solution No.32 is:
12 23 31 31
Solution No.33 is:
12 23 31 32
Solution No.34 is:
12 23 32 32
Solution No.35 is:
13 13 13 31
Solution No.36 is:
13 13 21 31
Solution No.37 is:
13 13 21 32
Solution No.38 is:
13 13 23 31
Solution No.39 is:
13 13 23 32
Solution No.40 is:
13 13 31 31
Solution No.41 is:
13 13 31 32
Solution No.42 is:
13 21 21 31
Solution No.43 is:
13 21 21 32
Solution No.44 is:
13 21 31 31
Solution No.45 is:
13 21 31 32
Solution No.46 is:
13 21 32 32
Solution No.47 is:
13 23 21 31
Solution No.48 is:
13 23 21 32
Solution No.49 is:
13 23 23 31
Solution No.50 is:
13 23 23 32
Solution No.51 is:
13 23 31 31
Solution No.52 is:
13 23 31 32
Solution No.53 is:
13 23 32 32
Solution No.54 is:
13 31 31 31
Solution No.55 is:
13 31 31 32
Solution No.56 is:
13 31 32 32
For length 6 the total number of solution is:301
Press any key to continue