NFA-DFA代码C++

#include<iostream> #include<algorithm> #include<string> #include<stack> #include<queue> using namespace std; const int State_Num=10;//状态数目 char State[State_Num][State_Num+1];//记录各状态之间的转换关系 int tem[State_Num];//保存move函数进行之后所产生的集合 int T[State_Num];//保存函数closure进行之后所产生的集合 int Set_Num=0;//NFA到DFA转换过程中产生的不同状态的数目 char str[7]={'A','B','C','D','E','F'}; int Set_State[7][State_Num];//保存DFA状态的二维数组 int Dstates[7];//记录DFA的状态是否被标记 int Dtran[7][2];//保存各个状态之间输入a,b后的转换表 int Set_Value; void move(int n, int m) { memset(tem,0,State_Num*sizeof(int)); int i,j; for (i=0;i<State_Num;i++) { if (Set_State[n][i]==1) { for (j=0;j<State_Num;j++) if ((m==0&&State[i][j]=='a')||(m==1&&State[i][j]=='b')) tem[j]=1; } } } void Closure() { memset(T,0,State_Num*sizeof(int)); stack<int> s; int i; for (i=0;i<State_Num;i++) { T[i]=tem[i]; if (T[i]==1) s.push(i); } while(!s.empty()) { int t=s.top(); s.pop(); for (i=0;i<State_Num;i++) { if (State[t][i]=='#'&&T[i]==0) { T[i]=1; s.push(i); } } } } bool Is_New_State() { int num=0,overlap=0,i,j; for(i=0;i<Set_Num+1;i++) { num=0; for (j=0;j<State_Num;j++) if (T[j]!=Set_State[i][j]) num++; if (num==0) { overlap++; Set_Value=i; break; } } if (overlap>0) return false; else return true; } void Dtran_State() { Dtran[0][0]=0; Dtran[0][1]=0; Closure(); int i; for (i=0;i<State_Num;i++) Set_State[0][i]=T[i]; /* for (int qq=0;qq<10;qq++) cout<<Set_State[0][qq]<<" "; cout<<endl;*/ queue<int> q; q.push(0); while(q.size()) { int top_num; top_num=q.front(); q.pop(); move(top_num,0); //for (int qq=0;qq<10;qq++) //cout<<tem[qq]<<" "; //cout<<endl; Closure(); /*for (int qq=0;qq<10;qq++) cout<<T[qq]<<" "; cout<<endl;*/ if (Is_New_State()) { Set_Num++; Dtran[top_num][0]=Set_Num; for (i=0;i<State_Num;i++) Set_State[Set_Num][i]=T[i]; q.push(Set_Num); } else Dtran[top_num][0]=Set_Value; move(top_num,1); Closure(); if (Is_New_State()) { Set_Num++; Dtran[top_num][1]=Set_Num; for (i=0;i<State_Num;i++) Set_State[Set_Num][i]=T[i]; q.push(Set_Num); } else Dtran[top_num][1]=Set_Value; } } void main() { tem[0]=1; int i,j; for (i=0;i<State_Num;i++) for (j=0;j<State_Num;j++) State[i][j]='*'; for (i=0;i<State_Num;i++) State[i][i]='#'; State[0][1]='#'; State[0][7]='#'; State[1][2]='#'; State[1][4]='#'; State[3][6]='#'; State[5][6]='#'; State[6][1]='#'; State[6][7]='#'; State[2][3]='a'; State[4][5]='b'; State[7][8]='a'; State[8][9]='b'; /*Closure(); for (i=0;i<10;i++) cout<<T[i]<<" "; cout<<endl; for (i=0;i<State_Num;i++) Set_State[0][i]=T[i]; move(0,0); for (i=0;i<10;i++) cout<<tem[i]<<" "; cout<<endl; Closure(); for (i=0;i<10;i++) cout<<T[i]<<" "; cout<<endl; move(0,1); Closure(); for (i=0;i<10;i++) cout<<T[i]<<" "; cout<<endl; //Set_State[1][]={0,1,1,1,1,0,1,1,1,0}; Set_State[1][0]=0; Set_State[1][1]=1; Set_State[1][2]=1; Set_State[1][3]=1; Set_State[1][4]=1; Set_State[1][5]=0; Set_State[1][6]=1; Set_State[1][7]=1; Set_State[1][8]=1; Set_State[1][9]=0; move(1,1); Closure(); for (i=0;i<10;i++) cout<<T[i]<<" "; cout<<endl;*/ Dtran_State(); cout<<"状态"<<" 输入符号"<<endl; cout<<" a b"<<endl; for (i=0;i<Set_Num+1;i++) cout<<str[i]<<" "<<str[Dtran[i][0]]<<" "<<str[Dtran[i][1]]<<endl; }