01.cpp

编译原理NFA到DFA的转换源码

#include "iostream.h"

int c=0;//全局变量
//temp
void line(int s[],int n)//排序
{
	for(int i=1;i<n;i++)
		for(int j=i;(j>0)&&(s[j]<s[j-1]);j--)
		{
			int temp=s[j];
			s[j]=s[j-1];
			s[j-1]=temp;
		}
}

void out(int s[],int &n)//检查重复
{
	for(int i=0;i<n-1;i++)
		if(s[i]==s[i+1])
		{
			for(int j=i;j<n-1;j++) s[j]=s[j+1];
			n--;
			i--;
		}
}

template <class Elem> class stack
{
	private:
		int size;
		int top;
		Elem *listArray;
	public:
		stack(int sz=100)
		{	size=sz;top=0;listArray=new Elem[sz];}
		~stack()
		{	delete []listArray;}
		bool push(const Elem& item)
		{
			if(top==size) return false;
			else {listArray[top++]=item;return true;}
		}
		bool pop(Elem& it)
		{
			if(top==0) return false;
			else {it=listArray[--top];return true;}
		}
		int length() const {return top;}
};

void closure(int s[][100],int& n,int z[],int n0,int sub[],int& subn)//数组的闭包
{
	stack<int>t;
	int i=0;
	for(int m=0;m<n0;m++)
	{
		t.push(z[m]);
		sub[i++]=z[m];
	}
	int a,mark=0;
	while(t.length())
	{
		t.pop(a);
		for(int j=0;j<n;j++)
			if(s[a][j]==2)
			{
				mark=0;
				for(int k=0;k<i;k++) if(sub[k]==j) mark=1;
				if(mark==0)
				{
					sub[i++]=j;
					t.push(j);
				}
			}
	}
	subn=i;//闭包的个数
	line(sub,i);//排序
}

void closure(int s[][100],int& n,int z,int sub[],int& subn)//初始状态的闭包
{
	stack<int>t;
	int i=0;
	t.push(z);
	sub[i++]=z;
	int a,mark=0;
	while(t.length ())
	{
		t.pop(a);
		for(int j=0;j<n;j++)
			if(s[a][j]==2)
			{
				mark=0;
				for(int k=0;k<i;k++) if(sub[k]==j) mark=1;
				if(mark==0)
				{
					sub[i++]=j;
					t.push(j);
				}
			}
	}
	subn=i;
	line(sub,i);
}

class DFA//DFA中的状态集合
{
	public:
		void add(int S[],int N)
		{
			for(int i=0;i<N;i++) s[i]=S[i];//初始化
			n=N;
			c++;
		}
		int s[100];
		int n;
		int next0;//零的出边
		int next1;//一的出边
};

bool eq(DFA a,DFA b)
{
	if(a.n!=b.n) return false;
	else
	{
		for(int i=0;i<a.n;i++) if(a.s[i]!=b.s[i]) return false;
	}
	return true;
}
	
void main()
{
	int s[100][100];
	
	
	cout<<"请输入NFA的状态数目：";
	int n;
	cin>>n;
	
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++) s[i][j]=-1;
	cout<<"请输入0边的数目：";
	int b0;
	cin>>b0;
	int start,end;
	for(i=0;i<b0;i++)
	{
		cout<<"请输入第"<<i+1<<"条0边：";
		cin>>start>>end;
		s[start][end]=0;
	}
	cout<<"请输入1边的数目：";
	int b1;
	cin>>b1;
	for(i=0;i<b1;i++)
	{
		cout<<"请输入第"<<i+1<<"条1边：";
		cin>>start>>end;
		s[start][end]=1;
	}
	cout<<"请输入E边的数目：";
	int bE;
	cin>>bE;
	for(i=0;i<bE;i++)
	{
		cout<<"请输入第"<<i+1<<"条E边：";
		cin>>start>>end;
		s[start][end]=2;
	}
	cout<<"请输入开始状态：";
	int Start;
	cin>>Start;
	cout<<"请输入中止状态数目：";
	int N;
	cin>>N;
	int *End=new int[N];
	cout<<"请输入中止状态：";
	for(i=0;i<N;i++) cin>>End[i];
	
	
	int sub[100],subn,tt[100],j,k,l,w=0,sign;
	
	
	closure(s,n,Start,sub,subn);//初始状态的闭包
	
	DFA *dfa=new DFA[100],temp,temp2;//DFA的状态数组以及两个对象
	
	for(i=0;i<100;i++) 
	dfa[i].next0=dfa[i].next1=-1;
	dfa[c].add(sub,subn);// C：全局变量，初始值为零
	
	stack<DFA>t;
	t.push(dfa[0]);//初始状态的闭包入栈
	while(t.length())
	{
		t.pop(temp);
		for(i=0;i<2;i++)
		{
			for(j=0;j<temp.n;j++)//temp.n：DFA状态的数目
				for(k=0;k<n;k++)//对每一个输入的状态进行检查（零或一）
					if(s[(temp.s[j])][k]==i)
					{
						tt[w++]=k;//求MOVE
						continue;
					}
			closure(s,n,tt,w,sub,subn);//对MOVE作闭包
			temp2.add(sub,subn);
			c--;
			for(l=0;!(eq(temp2,dfa[l]))&&(l<c);l++);//DFA数组中检查是否有重复的项
			if(l==c) sign=0;
			else sign=1;
			if(sign==0)
			{
				dfa[c].add(sub,subn);//生成一个新的DFA状态集合
				t.push(dfa[c-1]);//将另一个
			}
			for(int m=0;!(eq(temp,dfa[m]));m++);
			if((i==0)&&(sign==1)) dfa[m].next0=l;
			if((i==1)&&(sign==1)) dfa[m].next1=l;
			if((i==0)&&(sign==0)) dfa[m].next0=c-1;
			if((i==1)&&(sign==0)) dfa[m].next1=c-1;
			w=0;		
		}
	}

	cout<<"*************************************************************************"<<endl<<endl;
	cout<<"1.状态的集合："<<endl;
	for(i=0;i<c;i++)
	{
		cout<<"DFA状态"<<i<<":"<<"{ ";
		for(j=0;j<dfa[i].n;j++) cout<<dfa[i].s[j]<<" ";
		cout<<"}"<<endl;
	}
	cout<<endl;
	cout<<"2.输入符号集合："<<endl<<"{ 0 1 }"<<endl<<endl;
	cout<<"3.关系："<<endl;
	cout<<"状态\t"<<"输入符号\t"<<endl<<'\t'<<"0\t"<<"1\t"<<endl;
	for(i=0;i<c;i++)
	{
		cout<<i<<'\t';
		if(dfa[i].next0!=-1) cout<<dfa[i].next0<<'\t';
		else cout<<"无\t";
		if(dfa[i].next1!=-1) cout<<dfa[i].next1<<endl;
		else cout<<"无"<<endl;
	}
	cout<<endl;
	cout<<"4.开始状态："<<endl<<"{ ";
	for(i=0;i<c;i++)
		for(j=0;j<dfa[i].n;j++)
			if(dfa[i].s[j]==Start) cout<<i<<" ";
	cout<<"}"<<endl<<endl;
	cout<<"5.终止状态："<<endl<<"{ ";
	l=0;
	for(i=0;i<c;i++)
		for(j=0;j<dfa[i].n;j++)
			for(k=0;k<N;k++)
			{
				if(dfa[i].s[j]==End[k]) tt[l++]=i;
			}
	line(tt,l);
	out(tt,l);
	for(i=0;i<l;i++) cout<<tt[i]<<" ";
	cout<<"}"<<endl;
}