NFA确定化.doc

学号：专业：姓名： 实验日期：2012.4.27教师签字：成绩：实验名称：试验四：DFA的确定化 实验目的：1. 掌握FA的结构。2. 熟悉DFA向NFA转化的方法。3. 掌握子集法确定化DFA。实验原理：1. 一个自动机是一个五元组，分别是2. 使用子集法的步骤是：1) 将起始状态求闭包，得到S0。2) 将S0做f函数转换，得到在任意符号集元素下的状态集。3) 对状态集求空闭包，并以空闭包为终点，记录mov函数。4) 如果空闭包不存在，将空闭包记录。5) 循环2至5直到新产生的空闭包不再被记录。实验内容：.实验要求：输入一个NFA，得到一个DFA。实验代码：#include #include #include #include using namespace std;struct moveint front;/开始状态char second;/遇到的字符int last;/最后的状态;vector v_move;/记录空关系的move函数struct b_e /开始状态与结束状态int _begin;vector _end;struct favector v_status;string _cigma;vector v_move;b_e _b_e;dfa,nfa;struct closurevector s;vector v_closure;/记录新闭包项目/bool cmp(const int a,const int b)return ab;void print()coutNFA转化为DFA COPYRIGHT FROM NINGYU 2012/4/27endl;void init()print();cout请输入五元组的NFA信息，每个格式固定如下endl;int s;cout输入状态集，以-1结束s,s!=-1)nfa.v_status.push_back(s);cout输入字符集，以回车换行结束nfa._cigma;cout请输入move函数，以Ctrl+Z结束_m.front_m.second_m.last,_m.front!=-1)nfa.v_move.push_back(_m);if(_m.second=#)v_move.push_back(_m);cout请输入开始态与结束态nfa._b_e._begin;while(cins1)nfa._b_e._end.push_back(s1);void print_fa(fa fa1)/打印facout新fa格式如下：endl状态集endl;for(int i=0;ifa1.v_status.size();i+)coutfa1.v_statusi ;coutendl符号集合endlfa1._cigmaendlmove函数endl;for(int i=0;ifa1.v_move.size();i+)coutmove(fa1.v_movei.front,fa1.v_movei.second)=fa1.v_movei.lastendl;cout初始态:fa1._b_e._beginendl终态:;for(int i=0;ifa1._b_e._end.size();i+)cout fa1._b_e._endi ;coutendlendlendl;/vector get_move(int a,char c)/得到move（a，c）的状态，如果没有，返回-1;vector t;for(int i=0;infa.v_move.size();i+)if(nfa.v_movei.front=a&nfa.v_movei.second=c)t.push_back(nfa.v_movei.last);return t;int find_closure(closure c)/查找闭包项是否存在，如果存在，返回所在下标，如果不存在，返回-1；for(int i=0;iv_closure.size();i+)if(c.s.size()!=v_closurei.s.size()continue;int j;for(j=0;jc.s.size();j+)if(c.sj!=v_closurei.sj)break;if(j!=c.s.size()continue;else return i;return -1;int find_closure(closure c,int t)/在闭包c中查找元素t，如果找到，返回下标，如果未找到，返回-1;for(int i=0;ic.s.size();i+)if(c.si=t)return i;return -1;closure get_closure(closure c)/返回闭包c的闭包项/有问题for(int i=0;ic.s.size();i+)for(int j=0;jv_move.size();j+)if(c.si=v_movej.front&find_closure(c,v_movej.last)=-1)/如果查找到新闭包元素并且元素不再闭包项中,将元素添加进来c.s.push_back(v_movej.last);sort(c.s.begin(),c.s.end(),cmp);return c;closure clo_move(closure c,char a)/对于一组状态，得到它关于字符a的move状态后的状态集closure t;vector p;for(int i=0;ic.s.size();i+)p=get_move(c.si,a);if(p.size()=0)continue;else for(int j=0;jp.size();j+)if(find_closure(t,pj)=-1)t.s.push_back(pj);sort(t.s.begin(),t.s.end(),cmp);return t;bool get_endStatues(int p)/查找p状态是否为dfa终态，如果是，返回true，否则，false;for(int i=0;iv_closurep.s.size();i+)for(int j=0;jnfa._b_e._end.size();j+)if(v_closurep.si=nfa._b_e._endj)return true;return false; void tran_fa()/fa的确定化函数，做闭包，看move函数;int count=-1;closure c;/初始化c.s.push_back(nfa._b_e._begin);c=get_closure(c);dfa._b_e._begin=0;dfa._cigma=nfa._cigma;dfa.v_status.push_back(0);v_closure.push_back(c);count+;/closure c1;struct move m1;while(countv_closure.size()/当新建闭包项中还剩余有未move的函数，进行计算c=v_closurecount;for(int i=0;infa._cigma.length();i+)c1=clo_move(c,nfa._cigmai);c1=get_closure(c1);/求闭包;int last1=find_closure(c1);if(last1!=-1)/闭包项已存在m1.front=count;m1.second=nfa._cigmai;m1.last=last1;dfa.v_move.push_back(m1);/插入移动函数else /闭包项不存在v_closure.push_back(c1);dfa.v_status.push_back(dfa.v_status.size();/将新产生的状态记录，然后记录move函数;m1.front=count;m1.second=nfa._cigmai;m1.last=dfa.v_status.size()-1;dfa.v_move.push_back(m1);/插入移动函数count+;for(int i=0;iv_closure.size();i+)if(get_endStatues(i)dfa._b_e._end.push_back(i);int main()init();print_f