NFA转换为DFA子集构造法

本人自己花了一整天编的NFA转换为DFA的程序，算法来至编译原理教材（陈意云）

// NFA转为DFA.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h“
#include
#include
#include
#include
#include
using namespace std;
struct edge{
	int startend;
	char c;
}E[100]Ekong[100];//E保存所有的边，Ekong保存转换字符为空的边
struct State{
	int H[100];//状态集合
	int count;//状态集合中的元素个数
	int flag;//是否是接受状态
	int mark;//状态编号
};
int n;//n:边数
int nk=0;//空字符转换的边数
int firstaccept;//开始状态，接受状态
char alpha[100];//输入字母表#代表空串
int numof_char=0;//字母表中的字符个数
int useof_char[256];//该转换字符是否用过
int f[200];//状态属性标志：0表示始态，1表示接受态，-1表示中间态
State DFA[100];//DFA状态集
int useof_DFA[100];//标志构造出来的状态是否已存在
int numof_Dtran=0;//最后得到的DFA中的状态数
char Dtran[100][100];//DFA状态转换表
void input（）
{
	int ise;
	char ch;
	cout<<“请输入转换的有向边数n：“<	cin>>n;
	cout<<“请输入NFA的开始状态：“<	cin>>first;
	cout<<“请输入NFA的接受状态（输入-1结束）：“<	memset（f-1sizeof（f））;
	memset（useof_char0sizeof（useof_char））;
	f[first]=0;
	cin>>accept;
	while（accept!=-1）
	{
		f[accept]=1;
		cin>>accept;
	}
	cout<<“请输入NFA起点，终点，转换字符（‘#‘表示空字符）：“<	int k=0;
	for（i=0;i	{
		cin>>s>>e>>ch;
		E[i].start=s;
		E[i].end=e;
		E[i].c=ch;
		if（ch!=‘#‘&&!useof_char[ch]）
		{
			alpha[numof_char++]=ch;
			useof_char[ch]=1;
		}
		if（ch==‘#‘）
		{
			Ekong[nk].start=s;
			Ekong[nk].end=e;
			Ekong[nk].c=ch;
			nk++;
		}
		
	}
}
State move（State Tchar s）//c!=‘#‘
{
	State temp;
	temp.count=0;
	/*temp.flag=0;*/
	temp.mark=T.mark;
	int ij=0k=0;
	for（i=0;i	{
		j=0;
		while（j		{
			if（E[j].start==T.H[i]&&E[j].c==s）
			{
				temp.H[temp.count++]=E[j].end;
			}
			
			j++;
		}
	}
	return temp;
}
void arriveBynone（int tint result[]int& num）//搜索状态t通过一个或多个空字符到达的状态结果存在result中
{
	int k=0;
	int m=0;
	num=0;
	stack S;
	S.push（t）;
	int j;
	while（!S.empty（））
	{
		j=S.top（）;
		S.pop（）;
		m=0;
		while（m		{
			if（Ekong[m].start==j）
			{
				result[num++]=Ekong[m].end;
				S.push（Ekong[m].end）;
			}
			m++;
		}
	}
}
bool check（int iState T）//判断状态i是否在T中
{
	int j;
	for（j=0;j	{
		if（T.H[j]==i）
			return true;
	}
	return false;
}
State closure（State T）//求闭包
{
	stack STACK;
	State temp;
	int ijk;
	for（i=0;i	{
		STACK.push（T.H[i]）;
		temp.H[i]=T.H[i];
	}
	temp.count=T.count;
	/*temp.flag=0;*/
	temp.mark=T.mark;
	
	while（!STACK.empty（））
	{
		int t=STACK.top（）;
		STACK.pop（）;
		//搜索状态t通过一个或多个空字符到达的状态
		int search_result[100];
		int num;
		arriveBynone（tsearch_resultnum）;
		for（j=0;j		{
			if（!check（search_result[j]temp））
			{
				temp.H[temp.count++]=search_result[j];
				STACK.push（search_result[j]）;
			}
		}
	}
	for（k=0;k	{
		if（f[temp.H[k]]==1）
		{
			temp.flag=1;
			break;
		}
		if（f[temp.H[k]]==0）
		{
			temp.flag=0;
			break;
		}
	}
	sort（temp.Htemp.H+temp.count）;
	for（i=0;i	{
		if（temp.count!=DFA[i].count）
			continue;
		sort（DFA[i].H

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

     文件      90112  2009-04-13 23:48  NFA转为DFA2\debug\NFA转为DFA.exe

     文件     735024  2009-04-13 23:48  NFA转为DFA2\debug\NFA转为DFA.ilk

     文件     781312  2009-04-13 23:48  NFA转为DFA2\debug\NFA转为DFA.pdb

     文件       5008  2009-05-07 20:45  NFA转为DFA2\NFA转为DFA\Debug\BuildLog.htm

     文件         67  2009-04-13 23:48  NFA转为DFA2\NFA转为DFA\Debug\mt.dep

     文件        403  2009-04-11 09:55  NFA转为DFA2\NFA转为DFA\Debug\NFA转为DFA.exe.embed.manifest

     文件        468  2009-04-11 09:55  NFA转为DFA2\NFA转为DFA\Debug\NFA转为DFA.exe.embed.manifest.res

     文件        385  2009-04-13 23:48  NFA转为DFA2\NFA转为DFA\Debug\NFA转为DFA.exe.intermediate.manifest

     文件     201462  2009-04-13 23:48  NFA转为DFA2\NFA转为DFA\Debug\NFA转为DFA.obj

     文件    1048576  2009-04-11 09:55  NFA转为DFA2\NFA转为DFA\Debug\NFA转为DFA.pch

     文件      10773  2009-04-11 09:55  NFA转为DFA2\NFA转为DFA\Debug\stdafx.obj

     文件     232448  2009-05-07 20:45  NFA转为DFA2\NFA转为DFA\Debug\vc80.idb

     文件     249856  2009-05-07 20:45  NFA转为DFA2\NFA转为DFA\Debug\vc80.pdb

     文件       5800  2009-05-07 20:45  NFA转为DFA2\NFA转为DFA\NFA转为DFA.cpp

     文件       4496  2009-04-11 09:42  NFA转为DFA2\NFA转为DFA\NFA转为DFA.vcproj

     文件       1427  2009-05-17 11:58  NFA转为DFA2\NFA转为DFA\NFA转为DFA.vcproj.ADMIN-BE3685C2E.admin.user

     文件       1419  2009-05-07 20:51  NFA转为DFA2\NFA转为DFA\NFA转为DFA.vcproj.SOFT-TECH-5.Administrator.user

     文件        968  2009-04-11 09:42  NFA转为DFA2\NFA转为DFA\ReadMe.txt

     文件        215  2009-04-11 09:42  NFA转为DFA2\NFA转为DFA\stdafx.cpp

     文件        276  2009-04-11 09:42  NFA转为DFA2\NFA转为DFA\stdafx.h

     文件      11264  2009-05-17 11:58  NFA转为DFA2\NFA转为DFA.ncb

     文件        901  2009-04-11 09:42  NFA转为DFA2\NFA转为DFA.sln

    ..A..H.     12288  2009-05-17 11:58  NFA转为DFA2\NFA转为DFA.suo

     目录          0  2009-04-13 23:48  NFA转为DFA2\NFA转为DFA\Debug

     目录          0  2009-04-11 18:36  NFA转为DFA2\debug

     目录          0  2009-05-17 11:59  NFA转为DFA2\NFA转为DFA

     目录          0  2009-05-17 11:55  NFA转为DFA2

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

              3394948                    27



............此处省略0个文件信息