DFA编程实现报告

实验一DFA的编程实现一、实验目的：通过本次实验，加深对DFA及其识别的语言的理解，学习对一般的DFA的表达方法与编程实现方法。二、实验任务：编写一个C语言程序，模拟实现DFA识别字符串的过程。三、实验内容：（1）DFA的输入；（2）DFA的存储与读写；（3）DFA的正确性检查；（4）DFA的语言集列表显示；（5）DFA的规则字符串判定；四、实验分析：DFA的初始化一个DFA的基本信息状态集、字符集、开始状态、结束状态集、状态转换表；在程序中状态集、字符集、开始状态、结束状态集都用string类型来表示，即可不用考虑用户输入内容的长度。但缺点是字符集只能是字符而不可以是字符串。状态转换表：为三个字符的字符串，第一个为当前状态，第二个为输入字符，第三个为下一状态。用vector容器存放转换函数的内容字符串判断初始化一个DFA，后可以通过一下算法判断一个字符串是否符合该DFA。判定算法概要：准备：开始状态s0,接受状态集F,状态转换表T(s,c),sS,cc=getchar();s=开始状态s0;while(c!=EOF)//输入未结束则循环…{s=T(s,c);if(s==NULL)error();c=getchar();}if(s接受状态集F)accept();elseerror();在实际编写代码中的体现为voididentify()//判断字符串{cout请输入字符串endl;stringstr;cinstr;inti=0;charpresent=StartStates;while(istr.length()){present=move(present,str[i]);//move函数即去遍历转换表，返回下个状态if(present=='N')//N即为move返回错误的状态，{break;}i++;}if(FinalStates.find(present)!=FinalStates.npos)//如果返回的状态用find函数属于最终状态集则表示识别cout该自动机识别此字符串endl;elsecout该自动机不识别此字符串endl;}对DFA的存储与读写将DNF的信息写入文件中，第一行：字符集；第二行：状态集;第三行：开始状态；第四行：结束状态集；以下行写入状态转换表按照既定的规定读取文件中的数据将其赋值，然后初始化DFA即可；DFA的语言集列表显示：这一个模块应该是这个实验中比较难的一部分了。我并没有使用while循环的这个做法。而是用函数递归，通过所有字符集的路径去遍历整个DFA。最后将符合条件的字符串输出；voidTraversal(charpresent,intN,stringstrass=)//遍历DFA的语言集列表{if(present=='N'||N0)//若路径已经大于N或者当前状态错误，停止递归return;N--;if(FinalStates.find(present)!=FinalStates.npos){cout该自动机识别字符串:strassendl;}for(inti=0;iAlphabet.length();i++){stringtemp;temp=strass;strass+=Alphabet[i];Traversal(move(present,Alphabet[i]),N,strass);strass=temp;}}递归终止条件的判断。当N--时，N小于0，或者遍历到无路可走是便终止遇到的问题:对于递归的终止条件写得不够明确。递归前对字符串赋值strass赋值，递归后应该还原，这一点没有想到。调试了很久。总结，对递归的具体编写还是不熟悉。目前的代码，字符集和状态只能是一个字符，若要优化可以用vectorstring容器存储即可；实验用例：实验结果：DFA的初始化判断字符串：显示小于N的语言集：读取DFA文件：五、实验总结：在这次实验中，学习对一般的DFA的表达方法与编程实现方法。对课本提供的算法有了更深刻的认识。在编写和调试代码的过程中对自身的编程能力也有了很大的提高。对自动机和其识别语言有了更透彻的理解。在动手编程之前一定要好好明确实验的理论准备和思路的理清，能帮助我们在实验过程中少走更多的弯路。总之在这次实验中收获很多，提高了动手能力和分析问题的能力。源代码：//构造一个DFA#includeiostream#includestring#includevector#includefstreamusingnamespacestd;classTransitionTable{public:charpresent;//当前状态charnext;//下一状态charinput;//输入字符TransitionTable(charP,charI,charD){present=P;next=D;input=I;}};classDFA{public:DFA(){cout1、手动输入，2、读取txt文件endl;intselect;cinselect;if(select==1)inti();if(select==2)read();}stringStates;//状态集charStartStates;//开始状态stringFinalStates;//结束状态集stringAlphabet;//字符集vectorTransitionTableTrans;//转换函数voidinti()//初始化自动机{cout请输入有限状态集S：endl;cinStates;cout请输入字符集A：endl;cinAlphabet;cout请输入转换函数MOVE--格式为：当前状态-输入字符-下一状态：(输入#结束输入)endl;intj=0;while(true){charinput[4];cininput;if(strcmp(input,#)==0)break;TransitionTableTemp(input[0],input[1],input[2]);Trans.push_back(Temp);}cout请输入开始状态集S0：endl;cinStartStates;cout请输入结束状态集F：endl;cinFinalStates;}voididentify()//识别字符串{cout请输入字符串：endl;stringstr;cinstr;inti=0;charpresent=StartStates;while(istr.length()){present=move(present,str[i]);//move函数即去遍历转换表，返回下个状态if(present=='N')//N即为move返回错误的状态，{break;}i++;}if(FinalStates.find(present)!=FinalStates.npos)//如果返回的状态用find函数属于最终状态集则表示识别cout该自动机识别此字符串endl;elsecout该自动机不识别此字符串endl;;}charmove(charP,charI)//move转换函数{for(inti=0;iTrans.size();i++){if(Trans[i].present==P&&Trans[i].input==I)returnTrans[i].next;}return'N';}voidread()//从txt文件中读取DNF的信息{chartemp[10];fstreamff(DNF.txt,ios::in);ff.getline(temp,10);Alphabet=temp;ff.getline(temp,10);States=temp;ff.getline(temp,10);StartStates=temp[0];ff.getline(temp,10);FinalStates=temp[0];while(!ff.eof()){ff.getline(temp,10);TransitionTableTemp(temp[0],temp[1],temp[2]);Trans.push_back(Temp);}}/*将DNF的信息写入文件中，第一行：字符集；第二行：状态集;第三行：开始状态；第四行：结束状态集；以下行写入状态转换表*/voidwrite(){fstreamff(DNF.txt,ios::out);ffAlphabetendl;ffStatesendl;ffStartStatesendl;ffFinalStatesendl;for(inti=0;iTrans.size();i++)ffTrans[i].presentTrans[i].inputTrans[i].nextendl;ff.close();}voidTraversal(charpresent,intN,stringstrass=)//遍历DFA的语言集列表显示{if(present=='N'||N0)return;N--;if(FinalStates.find(present)!=FinalStates.npos){cout该自动机识别字符串:strassendl;}elseif(FinalStates.find(present)==FinalStates.npos&&N0)return;for(inti=0;iAlphabet.length();i++){stringtemp;temp=strass;strass+=Alphabet[i];Traversal(move(present,Alphabet[i]),N,strass);strass=temp;}}};intmain(){DFAexample;example.identify();intN;cout请输入Nendl;cinN;example.Traversal(example.StartStates,N);example.write();system(pause);return0;}/*测试用例输入状态转换表0a10b21b22a11a32b33a33b3#0a10b22a11b21a32b53a35b53b45a66b44a66a34b5*/