#include
#include
#include
using?namespace?std;
#define?max?100
int?n;//NFA的邊數(shù)
vector?value;

struct?edge{
????string?first;//邊的初始結(jié)點(diǎn)
	string?condition;//邊上的條件
	string?last;//邊的終點(diǎn)
};


string?closure（string?aedge?*b）//求狀態(tài)集合I的&-閉包，用&代替“空“
{
	int?ij;
	for（i=0;i	{
		for（j=0;j		{
			if（b[j].first[0]==a[i]&&b[j].condition==“&“）
			{
				a=a+b[j].last[0];
			}
		}
	}
	return?a;
}

string?move（string?collectionchar?chedge?*b）//狀態(tài)集合I的a弧轉(zhuǎn)換
{
	int?ij;
	string?s=““;
	for（i=0;i	{???
		for（j=0;j		{
			if（b[j].first[0]==collection[i]&&b[j].condition[0]==ch）
			???s=s+b[j].last;
		}
	}
	return?s;
}

string?sort（string?t）//字符串排序
{
	int?kij;
	char?tt;
	for（i=0;i	{
		k=i;
		for（j=i+1;j		{
			if（t[j]		}
		tt=t[k];t[k]=t[i];t[i]=tt;
	}
	return?t;
}


void?main（）
{
???int?ijx=0hlengthmd=0;
???string?Condition;//邊上的條件
???string?FirstLast;//初態(tài)，終態(tài)，
???string?T[max]ss;
???edge?*b=new?edge[max];
???cout<<“...................編譯原理實(shí)驗(yàn)五：有窮自動(dòng)機(jī)的確定化....................“<???cout<<“請(qǐng)輸入各邊信息：起點(diǎn)??條件（空用&表示）?終點(diǎn)?并以輸入#結(jié)束！！“<???for（i=0;i???{
	???cin>>b[i].first;
	???if（b[i].first==“#“）break;
	???else
		???cin>>b[i].condition>>b[i].last;
???}
???n=i;
???cout<<“請(qǐng)輸入NFA的初態(tài)及終態(tài)：“<???cin>>First>>Last;
???cout<<“請(qǐng)輸入NFA狀態(tài)中的輸入符號(hào)即邊上的條件:“<???cin>>Condition;
???T[x]=closure（Firstb）;//字符串?dāng)?shù)組存儲(chǔ)空閉包并排序
???T[x]=sort（T[x]）;
???value.push_back（0）;
???i=0;
???while（value[i]==0&&value.size（））
???{???
	???value[i]=1;
	???for（j=0;j	???{
		???ss=““;
		???ss=move（T[i]Condition[j]b）;
		???length=value.size（）;
		???for（h=0;h		???{
		??????if（T[h]==sort（closure（ssb）））break;
???????????}
		???if（h==length）
		?????{
			??????T[++x]=sort（closure（ssb））;
			??????value.push_back（0）;
		?????}
		???
	???}
	???i++;
???}
???edge?*DFA=new?edge[max];
???for（i=0;i<=x;i++）//構(gòu)造DFA的各邊
???{
	???for（j=0;j	???{
		???DFA[d].first=T[i];
		???DFA[d].condition=Condition[j];
		???ss=““;
		???ss=sort（closure（move（T[i]Condition[j]b）b））;
		???for（m=0;m<=x;m++）
			???if（ss==T[m]）DFA[d++].last=T[m];
	???}
???}
???cout<<“NFA構(gòu)造的DFA的各邊信息如下：“<???for（i=0;i???{
	???for（m=0;m<=x;m++）
	???{
		???if（DFA[i].first==T[m]）cout<	???}
	???for（m=0;m<=x;m++）
		???if（DFA[i].last==T[m]）cout<<“?????“<???}
???cout<<“確定后的DFA的初態(tài)為：“;
???for（m=0;m<=x;m++）
???{
	???for（j=0;j	???{
		???ss=T[m];
		???if（ss[j]==First[0]）cout<	???}
???}
???cout<<“確定后的DFA的終態(tài)為：“;
????for（m=0;m<=x;m++）
???{
	???for（j=0;j	???{
		???ss=T[m];
		???if（ss[j]==Last[0]）cout<	???}
???}
	cout<??system（“pause“）;
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????文件????????3149??2014-05-21?16:33??5.cpp
?????文件???????62464??2015-12-13?20:42??編譯原理實(shí)驗(yàn)五：有窮自動(dòng)機(jī)的確定化.doc