//?NFA轉(zhuǎn)為DFA.cpp?:?定義控制臺應(yīng)用程序的入口點。
//

#include?“stdafx.h“
#include
#include
#include
#include
#include
using?namespace?std;
struct?edge{
	int?startend;
	char?c;
}E[100]Ekong[100];//E保存所有的邊，Ekong保存轉(zhuǎn)換字符為空的邊
struct?State{
	int?H[100];//狀態(tài)集合
	int?count;//狀態(tài)集合中的元素個數(shù)
	int?flag;//是否是接受狀態(tài)
	int?mark;//狀態(tài)編號
};
int?n;//n:邊數(shù)
int?nk=0;//空字符轉(zhuǎn)換的邊數(shù)
int?firstaccept;//開始狀態(tài)，接受狀態(tài)
char?alpha[100];//輸入字母表#代表空串
int?numof_char=0;//字母表中的字符個數(shù)
int?useof_char[256];//該轉(zhuǎn)換字符是否用過
int?f[200];//狀態(tài)屬性標志：0表示始態(tài)，1表示接受態(tài)，-1表示中間態(tài)
State?DFA[100];//DFA狀態(tài)集
int?useof_DFA[100];//標志構(gòu)造出來的狀態(tài)是否已存在
int?numof_Dtran=0;//最后得到的DFA中的狀態(tài)數(shù)
char?Dtran[100][100];//DFA狀態(tài)轉(zhuǎn)換表
void?input（）
{
	int?ise;
	char?ch;
	cout<<“請輸入轉(zhuǎn)換的有向邊數(shù)n：“<	cin>>n;
	cout<<“請輸入NFA的開始狀態(tài)：“<	cin>>first;
	cout<<“請輸入NFA的接受狀態(tài)（輸入-1結(jié)束）：“<	memset（f-1sizeof（f））;
	memset（useof_char0sizeof（useof_char））;
	f[first]=0;
	cin>>accept;
	while（accept!=-1）
	{
		f[accept]=1;
		cin>>accept;
	}
	cout<<“請輸入NFA起點，終點，轉(zhuǎn)換字符（‘#‘表示空字符）：“<	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ài)t通過一個或多個空字符到達的狀態(tài)結(jié)果存在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）//判斷狀態(tài)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ài)t通過一個或多個空字符到達的狀態(tài)
		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轉(zhuǎn)為DFA2\debug\NFA轉(zhuǎn)為DFA.exe

?????文件?????735024??2009-04-13?23:48??NFA轉(zhuǎn)為DFA2\debug\NFA轉(zhuǎn)為DFA.ilk

?????文件?????781312??2009-04-13?23:48??NFA轉(zhuǎn)為DFA2\debug\NFA轉(zhuǎn)為DFA.pdb

?????文件???????5008??2009-05-07?20:45??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\BuildLog.htm

?????文件?????????67??2009-04-13?23:48??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\mt.dep

?????文件????????403??2009-04-11?09:55??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\NFA轉(zhuǎn)為DFA.exe.embed.manifest

?????文件????????468??2009-04-11?09:55??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\NFA轉(zhuǎn)為DFA.exe.embed.manifest.res

?????文件????????385??2009-04-13?23:48??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\NFA轉(zhuǎn)為DFA.exe.intermediate.manifest

?????文件?????201462??2009-04-13?23:48??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\NFA轉(zhuǎn)為DFA.obj

?????文件????1048576??2009-04-11?09:55??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\NFA轉(zhuǎn)為DFA.pch

?????文件??????10773??2009-04-11?09:55??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\stdafx.obj

?????文件?????232448??2009-05-07?20:45??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\vc80.idb

?????文件?????249856??2009-05-07?20:45??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug\vc80.pdb

?????文件???????5800??2009-05-07?20:45??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\NFA轉(zhuǎn)為DFA.cpp

?????文件???????4496??2009-04-11?09:42??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\NFA轉(zhuǎn)為DFA.vcproj

?????文件???????1427??2009-05-17?11:58??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\NFA轉(zhuǎn)為DFA.vcproj.ADMIN-BE3685C2E.admin.user

?????文件???????1419??2009-05-07?20:51??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\NFA轉(zhuǎn)為DFA.vcproj.SOFT-TECH-5.Administrator.user

?????文件????????968??2009-04-11?09:42??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\ReadMe.txt

?????文件????????215??2009-04-11?09:42??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\stdafx.cpp

?????文件????????276??2009-04-11?09:42??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\stdafx.h

?????文件??????11264??2009-05-17?11:58??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA.ncb

?????文件????????901??2009-04-11?09:42??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA.sln

????..A..H.?????12288??2009-05-17?11:58??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA.suo

?????目錄??????????0??2009-04-13?23:48??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA\Debug

?????目錄??????????0??2009-04-11?18:36??NFA轉(zhuǎn)為DFA2\debug

?????目錄??????????0??2009-05-17?11:59??NFA轉(zhuǎn)為DFA2\NFA轉(zhuǎn)為DFA

?????目錄??????????0??2009-05-17?11:55??NFA轉(zhuǎn)為DFA2

-----------?---------??----------?-----??----

??????????????3394948????????????????????27



............此處省略0個文件信息