用C语言实现NFA到DFA的转换过程

用C语言实现NFA到DFA的转换过程 NFA (nondeterministic finite-state automata)是不确定性有限状态自动机的简写，NFA的定义为： 一个不确定性有限状态自动机由以下部分所组成： A. 一个有限的输入字符集I B. 一个有限的状态集S C. 状态转换函数f: S x I -> P(S)，P(S)为s的幂集 D. 一个结束状态集Q，Q是S的子集 E. 一个初始状态s0 (属于S) F. 表示为A(I, S, f, Q, s0) 与NFA相对应，DFA (deterministic finite-state automata)表示确定性有限状态自动机。与NFA不同，DFA不存在Epsilon转换，并且每一个状态转换函数的值只对应一个状态，即一个状态输入一个字符，只能有一个状态相对应。 NFA与DFA的区别 显然，DFA更加适合我们进行字符串匹配，因为输入一个字符，总能从一个状态确定地转换为另一个状态，直到终结状态。NFA一个输入可能对应多个状态，因此需要进行回溯，先尝试一条路径，发现走不通，再回退到原来的状态尝试另外一条路径，显然匹配算法不如DFA简单。 给定一个NFA，总有一个DFA与之对应，即一个NFA可以转换成一个等价的DFA，我们将使用子集构造算法实现NFA到DFA的转换。

#include 
#include 
#include 
#define MAX 10
#define INFINIT 32767
#define NumMaxChar 10
#define NumMAXTN 10 


///////////////////////////////数据结构定义////////////////////////////////// 

//////////////////////////NFA图结构//////////////////////////////////
typedef struct edge
{//边
	int dest;
	char cost;
	struct edge *link;	//指向下一边
}*Edge; 

typedef struct vertex
{//顶点
	char data;	//状态
	Edge adj;	//边
}*Vertex; 

typedef struct graph
{//图
	Vertex NodeTable;
	int NumVertex;
	int MaxNumVertex;
	int NumEdge;
}*Graph;
//////////////////////////////////////////////////////////////////////
//////////////////////////状态转换表机构//////////////////////////////
typedef struct tablenode
{//转换表节点
	char newname;//新命名
	char ch[MAX];//顶点集合
}*TableNode; 

typedef struct tablequeue
{//转换表列
	TableNode TN[MAX];//转换表节点数组
	char transword;//转换条件
	int NumTn;//添加的顶点数
}*TableQueue; 

typedef struct transmatrix
{//状态转换矩阵
	TableQueue TQ;//转换表列组
	int transnum;//转换表列数
}*TranMatrix; 

///////////////////////////////////////////////////////////////////////////// 


///////////////////////////////////图操作////////////////////////////////////  
int GraphEmpty（Graph g）
{//图判空
	return g->NumVertex==0;
} 

int GraphFull（Graph g）
{//判图满
	return g->NumVertex==g->MaxNumVertex;
} 

char GetValue（Graph gint i）
{//寻找下标为i的顶点
	return （i>0 && iNumVertex? g->NodeTable[i].data:‘ ‘）;
}
  

void Insert_Vertex（Graph gchar vertex）
{//插入新的顶点
	g->NodeTable[g->NumVertex].data=vertex;
	g->NodeTable[g->NumVertex].adj=NULL;
	g->NumVertex++;
} 

void Insert_Edge（Graph gint v1int v2char weight）
{//插入边
	Edge p;
	p=（Edge）malloc（sizeof（struct edge））;
	p->cost=weight;
	p->dest=v2;
	p->link=g->NodeTable[v1].adj;
	g->NodeTable[v1].adj=p; 
} 

int GetVertexPos（Graph gchar v）
{//得到顶点在图中的下标
	int i=0;
	while（iNumVertex）
	{
		if（g->NodeTable[i].data==v）
		return i;
		i++;
	}
	return INFINIT;
} 

void Construct_Graph（Graph g）
{//创建图
	int kjivexnedgen;
	char headtailname;
	char weight;
	g->NumVertex=0;
	g->NumEdge=0;
	g->MaxNumVertex=MAX;
	g->NodeTable=（Vertex）malloc（（g->MaxNumVertex）*sizeof（struct vertex））;
	printf（“输入NFA状态数:“）;
	scanf（“%d“&vexn）;
	printf（“输入NFA状态名称:\n“）;
	flushall（）;
	//依次获取状态名称，并将这些顶点插入图中
	for（i=0;i	{  
		scanf（“%c“&name）;
		flushall（）;
		Insert_Vertex（gname）;
	}
    printf（“输入NFA的边数:“）;
    scanf（“%d“&edgen）;
    printf（“输入 起始状态，接受字符 和 到达状态:\n“）;
    flushall（）;
	//依次获取边的信息（起始顶点，接受字符，到达的顶点），并将这些边插入图中
	for（i=0;i	{   
		flushall（）;
		scanf（“%c %c %c“&tail&weight&head）;
		k=GetVertexPos（gtail）;
		j=GetVertexPos（ghead）;
		Insert_Edge（gkjweight）;
	}
} 

void Destruct_Graph（Graph g）
{//销毁图  
	int i;
	Edge p;
	for（i=0;iNumVertex;i++）
	{
		p=g->NodeTable[i].adj;
		while（p!=NULL）
		{
			g->NodeTable[i].adj=p->link;
			p->link=NULL;
			free （p）;
			p=g->NodeTable[i].adj;
		}
	}
	g->N

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       9191  2008-11-27 20:02  aa.cpp

----------- ---------  ---------- -----  ----

                 9191                    1