NFA转DFA 非确定有限自动机确定化（利用子集法构造DFA）

/** *NFA转DFA */ #include <iostream> #include <string> #include <stack> //定义最大的数组值 #define MAXS 100 #define START 0 //状态的开始状态标志 #define ACCEPT 1//状态的接受状态标志 #define MARKED 0//标记 #define UNMARKED 1//未标记 using namespace std; //状态s struct s { string s_name; //s的标号名字 int s_state; //s的状态（开始状态0/接受状态1） }START_STATE; //开始状态 //边 struct edge { s startNode; s endNode; string transSymbol; }EDGE[MAXS],EMPTY_EDGE[MAXS],NOT_EMPTY_EDGE[MAXS]; //状态集合T struct T { string T_name; string UP_T_name; //通过转换符获得此状态的状态名（可以说是父状态名） string T_transSymbol; //转换符 s s_set[MAXS]; int T_size; int T_flag; //T的标志位，标识T是否被标记，!!!!采用栈的运算，此标志位暂时不用 }NFA_T,DFA_T[MAXS]; //转换符 string TRANSSYMBOL[MAXS]; /*数据结构的定义*/ int TRANS_SYMBOL_COUNT = 0; //转换符的个数 int EMPTY_EDGE_COUNT = 0; //空转换边的个数 int NOT_EMPTY_EDGE_COUNT = 0; int EDGE_COUNT = 0; //总的有向边的个数 int DFA_SET_COUNT = 0; //方法声明 void input(); void print(); //将T中s进行排序，为后面的检查是否存在重复T提供保证。采用传址方式，同步修改 void sort(T&); int check_U_in_T(s ,T ); int check_Symbol_Exit(string); //下面两个T作为传入参数，不用引用方式，采用值传，因为要用这个新申请的空间作为新的返回值赋给另一个结构体 T getE_closure(T ); T get_closureByMove(T ,string); s get_State_by_StateName(string); void subsetConstructAlgorithm(); //检测新的状态集是否已经存在， int is_T_Exit(T); void main() { //应先初始化一下数组，先不处理，先靠int变量来控制 input(); //测试输入 /* cout<<"测试输出："<<endl; for(int i=0;i<NFA_T.T_size;i++) { cout<<"状态名："<<NFA_T.s_set[i].s_name<<" 状态的状态："<<NFA_T.s_set[i].s_state<<endl; } cout<<"有向边："<<endl; for(i=0;i<EDGE_COUNT;i++) { cout<<"边起点："<<EDGE[i].startNode.s_name<<" 边终点："<<EDGE[i].endNode.s_name<<" 边转换字符："<<EDGE[i].transSymbol<<endl; } cout<<"空向边："<<endl; for(i=0;i<EMPTY_EDGE_COUNT;i++) { cout<<"边起点："<<EMPTY_EDGE[i].startNode.s_name<<" 边终点："<<EMPTY_EDGE[i].endNode.s_name<<" 边转换字符："<<EMPTY_EDGE[i].transSymbol<<endl; } cout<<"转换字符："<<endl; for(i=0;i<TRANS_SYMBOL_COUNT;i++) { cout<<TRANSSYMBOL[i]<<endl; } */ subsetConstructAlgorithm(); //cout<<"DFA的状态集合个数："<<DFA_SET_COUNT<<endl; print(); } /* 通过状态名，返回状态 从NFA_T中获得（所有状态都在NFA_T里） */ s get_State_by_StateName(string state_name) { s state; for(int i=0;i<NFA_T.T_size;i++) { if(state_name.compare(NFA_T.s_set[i].s_name)==0) return NFA_T.s_set[i]; } cout<<"之前没有输入这个状态，到这肯定出现错误！"<<endl; return state; } /* 检查刚输入的符号是否已经在转换符号集中，已经存在返回1，否则0 */ int check_Symbol_Exit(string symbol) { int isExit = 0; if(symbol.compare("#")==0) { isExit = 1; return isExit; //输入空（#）直接返回 } for(int i=0;i<TRANS_SYMBOL_COUNT;i++) { if(symbol.compare(TRANSSYMBOL[i])==0) { //已经存在 isExit = 1; } } return isExit; } /* 输入程序，获取数据，建立NFA */ void input() { s get_state; cout<<"请输入开始状态编号（名字）"<<endl; cin>>get_state.s_name; get_state.s_state = START; NFA_T.s_set[NFA_T.T_size++] = get_state; START_STATE.s_name = get_state.s_name; START_STATE.s_state = START; cout<<"请输入接受状态编号（-1结束）"<<endl; cin>>get_state.s_name; get_state.s_state = ACCEPT; while(get_state.s_name.compare("-1")!=0) { //应检查输入状态不重复。暂时先不处理。 NFA_T.s_set[NFA_T.T_size++] = get_state; cin>>get_state.s_name; get_state.s_state = ACCEPT; } //输入边 cout<<"请输入转换的有向边数"; cin>>EDGE_COUNT; while(EDGE_COUNT<NFA_T.T_size-1) { cout<<"有向边数不应少于状态数！，请重新输入："<<endl; cin>>EDGE_COUNT; } //输入每一条边存入EDGE,是空转换状态时同时存入EMPTY_EDGE edge get_edge; string get_Name; for(int i=0;i<EDGE_COUNT;i++) { cout<<"请输入第"<<i+1<<"边的起始状态编号："<<endl; cin>>get_Name; get_edge.startNode = get_State_by_StateName(get_Name); cout<<"请输入第"<<i+1<<"边的终止状态编号："<<endl; cin>>get_Name; get_edge.endNode = get_State_by_StateName(get_Name); cout<<"请输入第"<<i+1<<"边的转换符号："<<endl; cin>>get_edge.transSymbol; if(check_Symbol_Exit(get_edge.transSymbol)==0) { TRANSSYMBOL[TRANS_SYMBOL_COUNT++] = get_edge.transSymbol; //cout<<"新转换符："<<TRANSSYMBOL[TRANS_SYMBOL_COUNT]<<endl; } EDGE[i] = get_edge; //若是空 存入EMPTY_EDGE if(get_edge.transSymbol.compare("#")==0) { EMPTY_EDGE[EMPTY_EDGE_COUNT++] = get_edge; //cout<<"新空边的起点："<<EMPTY_EDGE[EMPTY_EDGE_COUNT].startNode<<endl; } else { NOT_EMPTY_EDGE[NOT_EMPTY_EDGE_COUNT++] = get_edge; } } cout<<"输入结束！"<<endl; } /* 显示程序，输出DFA */ void print() { system("cls"); cout<<"DFA状态集合："<<endl; for(int i=0;i<DFA_SET_COUNT;i++) { cout<<"状态集合"<<DFA_T[i].T_name<<" 由状态集合 "<<DFA_T[i].UP_T_name<<" 通过转换符 "<<DFA_T[i].T_transSymbol<<" 获得;"<<endl; cout<<"包含状态为： { "; for(int j=0;j<DFA_T[i].T_size;j++) { cout<<DFA_T[i].s_set[j].s_name<<" "; } cout<<" }"<<endl; } } /* 排序，将E_closure中的状态s排序 */ void sort(T &t) { s temp;//交换变量 for(int i=0;i<t.T_size-1;i++) { for(int j=t.T_size-1;j>i;j--) { if(t.s_set[j].s_name.compare(t.s_set[j-1].s_name)<0) { temp = t.s_set[j]; t.s_set[j] = t.s_set[j-1]; t.s_set[j-1] = temp; } } } } //检测state是否在闭包中。已经存在返回1，否则0 int check_U_in_T(s state,T T) { int isExit = 0; for(int i=0;i<T.T_size;i++) { if(state.s_name.compare(T.s_set[i].s_name)==0) { //已经存在 isExit = 1; } } return isExit; } /* 获得E-closure闭包 T做为传入参数，同时作为返回参数。 */ T getE_closure(T T) { //将T中所有的状态压入栈stack中，将E_closure(T)初始化为T； stack<s> STACK; for(int i=0;i<T.T_size;i++) { STACK.push(T.s_set[i]); } //while栈stack不空 do begin while(!STACK.empty()) { //将栈顶元素弹出 s state = STACK.top(); STACK.pop(); //for 每个这样的状态u;从t到u有一条标记为 空E 的变 do for(int i=0;i<EMPTY_EDGE_COUNT;i++) { if(state.s_name.compare(EMPTY_EDGE[i].startNode.s_name)==0) { /*if u 不在E_closure(T)中do begin 将U添加到E_closure(T)； 将u压栈。 */ if(check_U_in_T(EMPTY_EDGE[i].endNode,T)==0)//不存在 { T.s_set[T.T_size++] = EMPTY_EDGE[i].endNode; STACK.push(EMPTY_EDGE[i].endNode); } } } } //先排序，便于以后的比较 sort(T); return T; } /* move(T,a)从T中的状态s经过输入符号a上的转换符可以到达的NFA状态集 */ T get_closureByMove(T TT,string transSymbol) { T moveClosure; moveClosure.T_size=0; moveClosure.UP_T_name = TT.T_name; moveClosure.T_transSymbol = transSymbol; for(int i=0;i<TT.T_size;i++) { for(int j=0;j<NOT_EMPTY_EDGE_COUNT;j++) { //边的转换符 符合 输入的转换符 if(TT.s_set[i].s_name.compare(NOT_EMPTY_EDGE[j].startNode.s_name)==0&&transSymbol.compare(NOT_EMPTY_EDGE[j].transSymbol)==0) { if(check_U_in_T(NOT_EMPTY_EDGE[j].endNode,moveClosure)==0)//不存在 { moveClosure.s_set[moveClosure.T_size++] = NOT_EMPTY_EDGE[j].endNode; } } } } return moveClosure; } /* 检测状态集是否已经存在，不存在返回0，存在返回1 */ int is_T_Exit(T check_T) { //检测范围在DFA_T中， int isExit = 0; for(int i=0;i<DFA_SET_COUNT;i++) { for(int j=0;j<DFA_T[i].T_size;j++) { //先判断大小是否相等，若不相等就没必要比较里面的状态是否相等 if(check_T.T_size==DFA_T[i].T_size) { int absolutely_equal = 1; //要确保对应顺序相同，此工作不在这实现，在生成T时就应该先排序。 for(int k=0;k<check_T.T_size;k++) { if(check_T.s_set[k].s_name.compare(DFA_T[i].s_set[k].s_name)!=0) {