将正规式R化成最小DFA的状态图.doc

姓名：沈亮 学号：0905080116 班级：09计算机工程01实验一：词法分析器的设计一、实验目的：（1）掌握词法分析器的构造过程以及基本方法。 （2）理解正规式、NFA、DFA及最小化DFA的转换过程和方法。二、实验内容给定一个正规式R=XY*|YX*Y|XYX，请先在练习本上将此正规式转变为NFA、DFA、最小化DFA；对你所完成的最小化DFA进行编程，完成词法分析器工作。三.设计分析1.将给定的正规式R=NFA；2.将NFA=DFA;3.将DFA=最小DFA;4，按照最小DFA的状态图，编写相应的程序。将正规式R=XY*|YX*Y|XYX化成最小DFA的状态图如下：图 1-1 最小DFA状态图简要方法：1. 根据最小DFA的状态图设计程序，从键盘输入含X、Y的字符串，所编写的程序从输入的字符串中的第一个字符开始比较，依次比较下去，若发现该字符串与该状态图不符，则不属于该状态图。2. 该程序的主要编程思想为大量使用if判断语句，以及一些简单的for循环语句。四、源程序代码：#includeusing namespace std;#define MAX 200void main()char aMAX;cout根据正规式R分成三个部分，即R1=XY*，R2=YX*Y，R3=XYXendl;cout请输入一段字符(仅含X或者Y):endl;cin.get(a,200);int n;/所输入字符串的长度for( int i=0;i!=MAX;+i)/计算编码的长度nif(ai=0)n=i;break;if(a0=X)if(a1=0) cout属于正规式R1=XY*endl;else if(a1=Y)if(a2=0)cout属于正规式R1=XY*endl;else if(a2=X & a3=0)cout属于正规式R3=XYXendl;else for(i=2;in;)if(ai=Y)i+;elsebreak;if(i=n)cout属于正规式R1=XY*endl;elsecout不属于正规式Rendl;elsecout不属于正规式Rendl;else if(a0=Y)if(a1=Y&a2=0)cout属于正规式R2=YX*Yendl;else if(an-1=Y)if(a1=X)for(i=1;in-1;)if(ai=X)i+;elsebreak;if(i=n-1)cout属于正规式R2=YX*Yendl;elsecout不属于正规式Rendl;elsecout不属于正规式Rendl;elsecout不属于正规式Rendl;五、测试用例1.当从键盘输入“XYYYYYYY“时，判断属于正规式R1=XY*.2.当从键盘输入YXXXXXXY时，判断属于正规式R2=YX*Y.3. 当从键盘输入XYX时，判断属于正规式R3=XYX.4. 当输入为XYYX时，不符合正规式R.5.当输入为YXXYX时，不符合正规式R.六、实验总结通过本次实验，使我对正规式转成相应的NFA、DFA以及最小DFA的知识更加了解，强化了我的理论知识，在实验过程中，还