n2d.cpp

一个自己写的NFA转DFA的程序

#include"iostream.h"
#include"n2d.h"
N2D::N2D()
{
	m=1;					//store the number of DFA state 
	DFA.resize(8);			//initialize DFA
	for(int j=0;j<8;j++)
		DFA[j].resize(2);
	NFA.resize(3);
	result.resize(8);		//set the maxisize size
	for(int i=0;i<3;i++)
		NFA[i].resize(2);			
	NFA[0][0].push_back(0);//initialize NFA
	NFA[0][0].push_back(1);
	NFA[0][1].push_back(1);
	NFA[0][1].push_back(-1);
	NFA[1][0].push_back(2);
	NFA[1][0].push_back(-1);
	NFA[1][1].push_back(2);
	NFA[1][1].push_back(-1);
	NFA[2][0].push_back(-1);
	NFA[2][0].push_back(-1);
	NFA[2][1].push_back(2);
	NFA[2][1].push_back(-1);		
	result[0].push_back(0);	
}
bool N2D::change()
{
	int v;
	push(0);
	while(1)
		if((v=pop())==-1)
			return 0;
		else
			Change(v);
}
bool N2D::check(int n)//check wether the state n has been exist;
{
	for(int i=0;i<n;i++)
	{
		if(result[i].size()!=result[n].size())		
			continue;
		for(int j=0;j<result[i].size();j++)
			if(result[i][j]!=result[n][j])
				break;
		if( j==result[i].size())
			return 0;	
	}
	return 1;
}
void N2D::sort(vector<int> &x)//sort the state x composed of set with increasing sequence though the bubble sort
{
	int temp;
	for(int i=0;i<x.size()-1;i++)
		for(int j=i;j<x.size()-1;j++)
			if(x[j]>x[j+1])
			{
				temp=x[j];
				x[j]=x[j+1];
				x[j+1]=temp;
			}
}
void N2D::push(int m)	//store the state into stack 
{
	s.push(m);
}
int N2D::pop()			//fetch the top data of the stack
{
	int temp;
	if(s.size()>0)
	{
		temp=s.top();
		s.pop();
		return temp;
	}
	else
		return -1;
}
void N2D::printNFA()
{
	cout<<"Discribe the NFA with planar table  as following:"<<endl;
	cout<<"note:coloum discribes char,row discribes state,-1 discribes NULL"<<endl;
	cout<<'\t'<<'0'<<'\t'<<'1'<<endl;
	for(int i=0;i<3;i++)
	{
		cout<<i;
		cout<<'\t';
		for(int j=0;j<2;j++)
		{
			for(int k=0;k<NFA[i][j].size();k++)
				cout<<NFA[i][j][k]<<' ';
			cout<<'\t';
		}
		cout<<endl;
	}
}
void N2D::printDFA()
{
	cout<<"Discribe the transformed DFA with planar table  as following:"<<endl;
	cout<<"note:coloum discribes char,row discribes state"<<endl;
	cout<<'\t'<<0<<'\t'<<'1'<<endl;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<result[i].size();j++)
			cout<<result[i][j];
		cout<<'\t';
		for(j=0;j<2;j++)
		{
			for(int k=0;k<DFA[i][j].size();k++)
				cout<<DFA[i][j][k];
			cout<<'\t';
		}
			cout<<endl;
	}
}
void N2D::Change(int x)//change the NFA state x to DFA state
{ 
	int v=0,label;
		for(int j=0;j<2;j++)//j is char 0 or 1
		{
			label=0;
			for(int t=0;t<result[x].size();t++)
			{
				for(int k=0;k<2;k++)
				{	
					if((v=NFA[result[x][t]][j][k])>=0)
					{
						if(v!=result[m][result[m].size()-1])//check wether every NFA state in DFA state m reach the same state for char 0 or 1
						{	
							DFA[x][j].push_back(v);//store the DFA information
							result[m].push_back(v);//store the DFA state
							label=1;
						}
					}
					else
						break;
				}
			}		
		if(label) // check wether the state has no output for first char 0 output
		{	
			sort(result[m]);
			if(!check(m))
			{		
				result[m].clear();//clear the repeated state	
				m--;	
			}
			else
			{	
			push(m);		
			}
			m++;
		}
		}	
}
void main()
{
	N2D n2d;
	n2d.change();
	n2d.printNFA();//print the result NFA
	n2d.printDFA();//print the result DFA
  }