复件 by2.cpp

对基于状态转换矩阵表示的FA转换成NFA

#include<iostream>
#include<fstream>
using namespace std;
typedef struct 
{
	int state1;
	char letter;
	int state2;
}transfor;
void move(int *a,transfor *b,char c);
int visit(int *v);
void  closure(int * a,transfor *b);
int include(int *a,int b);
//void  bing(int *a,int *b);
int equal(int *a,int *b);

void main()
{
	int k[20],a,endSigns[20];char letter[20],ch;
	int t[20][20],u[20];
	int visited[20];
	int IsEnd[20];//记录新产生的结束符集
	IsEnd[0]=0;//结束符集的个数
	int num=0;
	transfor condto[20]; 
	transfor newcondto[20];

	ifstream infile("f1.txt",ios::in);
	if(!infile)
	{
		cerr<<"open error!"<<endl;
		exit(1);
	}
	//输入初始值
//	cout<<"非终结符集(非终结符以数字表示,'-1'结束):"<<endl;
	infile>>a;
	int i=1;
	while(a>=0)
	{
		k[i++]=a;
		infile>>a;
	}
	k[0]=i-1;//统计非终结符个数
	//输入结束符集
//	cout<<"结束符集('-1'结束):"<<endl;
	infile>>a;
	i=1;
	while(a>=0)
	{
		endSigns[i++]=a;
		infile>>a;
	}
	endSigns[0]=i-1;//统计结束符个数
	//输入终结符集
//	cout<<"终结符集('#'结束)："<<endl;
	infile>>ch;
	i=1;
	while(ch!='#')
	{
		letter[i++]=ch;
		infile>>ch;
	}
	letter[0]=i-1;//统计终结符个数
//	cout<<"状态转换（'-1'结束）state1 a state2,e表示空):"<<endl;
	i=1;
	infile>>a;
	if(a>=0)
	{
		do
		{
	
		condto[i].state1=a;
		infile>>condto[i].letter;
		infile>>condto[i].state2;
//		cout<<"请输入下一个，-1结束"<<endl;
		infile>>a;
		i++;
		}while(a>=0);
		condto[0].state1=i-1;//统计状态转换个数
	}
	else
		condto[0].state1=0;

//NFA变换为DFA
	i=condto[0].state1;
	int newi=1,newj=2;
	u[0]=1;
	u[1]=k[1];
	newj=1;
	closure(u,condto);
	while(u[newj]>=0)
	{
		t[newi][newj]=u[newj];
		newj++;
	}
	t[newi][0]=newj-1;
	visited[0]=1;
	visited[1]=0;
	//查看该新状态是否是结束状态
	int circ=u[0];
	while(circ>0)
	{
		if(include(endSigns,u[circ]))
		{IsEnd[0]++; IsEnd[IsEnd[0]]=visited[0];break;}//将该状态添加至结束符
		circ--;
	}
	while(newi=visit(visited))
	{
		if(newi==-1)break;
		visited[newi]=1;//标记u
		//记录状态的个数
		newj=0;		
		
		i=letter[0];//设置循环次数为终结符的个数

		for(;i>0;i--)
		{
			if(letter[i]=='e')continue;
			for(int adj=t[newi][0];adj>=0;adj--)
			{u[adj]=t[newi][adj];}
			move(u,condto,letter[i]);
			if(u[0]==0)continue;
			closure(u,condto);
			if(u[0]!=0)
			{
				int p=visited[0],biao=0;//设置循环次数为已存在的状态数
				while(p>0)//看新产生的状态是否已存在
				{
					if(equal(t[p],u))
					{biao=1;break;}
					else
						p--;
				}
				if(biao==0)
				{
					newj=u[0];
					//查看该新状态是否是结束状态
					circ=u[0];
					while(circ>0)
					{
						if(include(endSigns,u[circ]))
						{IsEnd[0]++;IsEnd[IsEnd[0]]=visited[0];break;}//将该状态添加至结束符
						circ--;
					}
					while(newj>=0)
					{
						t[visited[0]+1][newj]=u[newj];
						newj--;
					}
					//t[visited[0]+1][0]=newj-1;	
					visited[0]++;
					visited[visited[0]]=0;
					//记录新状态 	
					newcondto[num].state1=newi-1;
					newcondto[num].letter=letter[i];
					newcondto[num].state2=visited[0]-1;
					num++;
				}
				else
				{
				newcondto[num].state1=newi-1;
				newcondto[num].letter=letter[i];
				newcondto[num].state2=p-1;
				num++;
				}
			}
		}//END OF for(;i>0;i--)
	}//END OF while(newi=visit(visited))
	for(i=0;i<num;i++)
	{
		cout<<newcondto[i].state1<<"  "<<newcondto[i].letter<<"  "<<newcondto[i].state2<<endl;
	}	
	cout<<"初态为0"<<endl;
	cout<<"结束符集：";
	for(i=IsEnd[0];i>0;i--)
	{cout<<IsEnd[i]<<"\t";}
	cout<<endl;
}

int equal(int *a,int *b)//返回值为1则表示相等，0表示不相等
{
	int i,j,flag=0;
	i=b[0];j=a[0];
	if(i==j)
	{
		for(;i>0;i--)
		{
			j=a[0];
			for(;j>0;j--)
			{
				if(a[j]==b[i])
					flag++;
			}
		}
		if(flag==a[0])
			return 1;
		else
			return 0;
	}
	else
		return 0;
}

int visit(int *v)
{
	int i=v[0];
	for(;i>=0;i--)
	{
		if(v[i]==0)
			return i;
	}
	return -1;
		
}

void  closure(int * a,transfor *b)
{
	int i=a[0],j=b[0].state1;
	int u[20];
	u[0]=0;
	int vis[20];
	vis[0]=a[0];
	for(;i>0;i--)//给vis赋初值,为未访问
	{
		vis[i]=0;
	}
	int newi;
	while(newi=visit(vis))
	{
		if(newi==-1)break;
		vis[newi]=1;
		j=b[0].state1;
		for(;j>0;j--)
		{
			if(b[j].state1==a[newi]&&b[j].letter=='e')
			{
				if(!include(a,b[j].state2))
				{a[0]++;a[a[0]]=b[j].state2;vis[a[0]]=0;vis[0]++;}
			}
		}
	}
}
int include(int *a,int b)
{
	int i=a[0];
	while(i)
	{
		if(a[i]==b)
			return 1;
		i--;
	}		
	return 0;
}

void move(int *a,transfor *b,char c)
{
	int i=a[0],j=b[0].state1,p[20];
	p[0]=0;
	for(;i>0;i--)
	{
		j=b[0].state1;
		for(;j>0;j--)
		{
			if(b[j].state1==a[i]&&b[j].letter==c)
			{
				if(!include(p,b[j].state2))
				{p[0]++;p[p[0]]=b[j].state2;}
			}
		}
	}
	for(i=a[0];i>=0;i--)
	{
		a[i]=-85993460;
	}
	for(i=p[0];i>=0;i--)
	{
		a[i]=p[i];
	}
}