simpledfamain.cpp

计算理论的经典算法

#include<iostream.h>

#define maxstate 20
#define maxletter 26

struct State {
	  int lastf;
	  int newf;
	  int num;
	  int kd;
};




void main()
{
   struct State sta[maxstate];
   char letter[maxletter];
   int nendstatenum;
   int endstatenum;
   int letternum;
   int move[maxstate][maxletter];
   
   cout<<"enter the number of letters:";         //输入字母表
   cin>>letternum;

   cout<<"enter your letter:";
   for(int i=0;i<letternum;i++)
	   cin>>letter[i];

   cout<<"enter none_endstate number:";     //输入非终结状态数目
   cin>>nendstatenum;
   cout<<"enter endstate number:";          //输入终结状态数目
   cin>>endstatenum;  

   int n;
   n=nendstatenum+endstatenum;

   cout<<"注意：起始状态设为0 状态"<<endl;
   int s;
   cout<<"enter the none_end_state"
	   <<"( 0--"<<n-1<<"):";           //输入非终结状态并初始化
   for(i=0;i<nendstatenum;i++)
   {  cin>>s;
      sta[s].lastf=0;
	  sta[s].newf=0;
	  sta[s].num=s;
      sta[s].kd=0;
   }

   cout<<"enter the end_state:"
	   <<"( 0--"<<n-1<<"):";           // 输入终结状态并初始化
   for(i=0;i<endstatenum;i++)
   {  cin>>s;
      sta[s].lastf=1;
	  sta[s].newf=1;
	  sta[s].num=s;
	  sta[s].kd=0;
   }

  
    
    cout<<"enter the state movement:"<<endl ;      //输入转移关系
    cout<<"  ";	  
    for(i=0;i<letternum;i++)
	  cout<<" "<<letter[i];
    cout<<endl;
 
   for(i=0;i<n;i++)
   {
	   cout<<sta[i].num<<"  ";
       for(int j=0;j<letternum;j++)
		   cin>>move[i][j];
   }

   int f=1;
   int temp=f;
   int endflag=1;
   while( endflag )
   {   int flag;
	   for(i=0;i<(temp+1);i++)                      //对每个等价类集合

		   for(int j=0;j<n;j++)                               //类集合内部的比较
		   {  flag=0;
		      if(sta[j].lastf==i)
				  
			   {  
			      for(int k=0;k<n;k++)
					  if(sta[k].lastf==sta[j].lastf&&sta[k].newf==sta[j].newf)      //若是在同一个等价类，继续测试
						  for(int t=0;t<letternum;t++)
						  {   int s1,s2;
						      s1=move[j][t];
							  s2=move[k][t];
							  
							  if(sta[s2].lastf!=sta[s1].lastf)  //出现分歧
							  {  sta[k].newf=f+1;      //  ??
							     flag=1;
                                 break;
							  }
							 
						  }
			   }

			   if(flag==1)
				   f++;
		   }
       for(i=0;i<n;i++)
		   if(sta[i].lastf==sta[i].newf)
			   ;
		   else
			   break;
		
	   if(i==n)         //若所有的状态等价类编号不再变化,退出while循环

         endflag=0;

	   for(i=0;i<n;i++)
			sta[i].lastf=sta[i].newf;
	   temp=f;
   }                                           //循环结束

                            
   
   cout<<"化简后的等价类数目:"<<temp+1<<endl;        //最终的等价类数目、等价类
   cout<<"化简成等价类集合 ---> 新的代替状态"<<endl;
   for(i=0;i<temp+1;i++)                    
   {   cout<<"{ ";
	   for(int j=0;j<n;j++)
		   if(sta[j].newf==i)
			   cout<<j<<" ";
		cout<<"} -->"<<i<<endl;
   }
 

   for (i=0;i<f+1;i++)                              //转化成新的状态机，刷新转移关系
	   for(int j=0;j<n;j++)
		   if(sta[j].newf==i)
			   for(int k=0;k<letternum;k++)
				   move[i][k]=sta[move[j][k]].newf;   //用等价类编号来代替等价类状态集合
   
   cout<<"新的状态转移图："<<endl;

   cout<<" ";	  
    for(i=0;i<letternum;i++)
	  cout<<"  "<<letter[i];
    cout<<endl;
 
   for(i=0;i<f+1;i++)
   {
	   cout<<i<<"  ";
       for(int j=0;j<letternum;j++)
		   cout<<move[i][j]<<"  ";
	   cout<<endl;
   }


  for(i=0;i<letternum;i++)             //检测是否含有不可达的状态
  {  int s0=sta[0].newf;
     sta[s0].kd=1;
      
     for(int j=0;j<f+1;j++)
	 { sta[move[s0][i]].kd=1;
       s0=move[s0][i];
	 }
  }

  int unreach=0;
  for(i=0;i<f+1;i++)
	  if(sta[i].kd==1)
		  ;
	  else                        //contain unreachble state
	  {  unreach=1;                                
		 cout<<"new state "<<i<<" can not reach"<<endl;
		 for (int j=0;j<letternum;j++)
			  move[i][j]=-1;
		 
	  }
  if(unreach==1)
  { cout<<"去掉不可达的状态后的转移："<<endl;         //若含有不可达状态，再次刷新转移关系
	
    cout<<" ";	  
    for(i=0;i<letternum;i++)
	  cout<<"  "<<letter[i];
    cout<<endl;
 
    for(i=0;i<f+1;i++)
    {  if(sta[i].kd==1)
	   { cout<<i<<"  ";
         for(int j=0;j<letternum;j++)
		   cout<<move[i][j]<<"   ";
	     cout<<endl;
	   }
	 }
  }
  else
	cout<<"  not contain unreachble state!"<<endl;

}