实验四 DFA程序实现.doc

班级: 学号: 姓名:实验三 DFA程序实现一、实验目的通过DFA程序的实现理解自动机的原理。二、实验重难点DFA编码实现三、实验内容与要求1、DFA的程序表示；四、实验学时2课时五、实验设备与环境 Visual C+ 6.0六、实验过程1There is an FA=（0,1,2,3, a,b, M, 0, 3） M： M(0,a)=1 M(0,b)=2 M(1,a)=3 M(1,b)=2 M(2,a)=1 M(2,b)=3 M(3,a)=3 M(3,b)=3 The question is how to judge whether the string “abbb” could be identified or accepted by the FA? 0 1 2 3 3参考代码：2. 以教材P72页习题3为例，确定化后的DFA为：构造该自动机的C语言程序表示；#includeint in(char s,char c,char e,char f)if(s=c)printf( Cnlook!the last status belongs to C!);return 1;else if(s=e)printf( Enlook!the last status belongs to E!);return 1;else if(s=f)printf( Fnlook!the last status belongs to F!);return 1;elsereturn 0;char step(char s,int t)if( t = 0)/判断数字经0转换成另一个数字switch(s)case s:return a;case a:return c;case b:return d;case c:return f;case d:return f;case e:return c;case f:return f;else if( t = 1)/判断数字经1转换成另一个数字switch(s)case s:return b;case a:return b;case b:return e;case c:return f;case e:return e;case f:return f;int realize(char *input)char c=c;char e=e;char f=f;int i;char s;s=s;for(i=0;inputi!=n;i+)printf(%2c,s);s=step(s,inputi);if(in(s,c,e,f)return 1;else return 0;main()int i;int a;char input40;printf(FA=(S,A,B,C,D,E,F,0,1,M,S,(C,F)n);/文法五元组printf(M:n);printf(M(S,0)=AM(S,1)=Bn);printf(M(A,0)=CM(A,1)=Bn);printf(M(B,0)=DM(B,1)=En);printf(M(C,0)=FM(C,1)=Fn);printf(M(D,0)=FM(D,1)=nulln);printf(M(E,0)=CM(E,1)=En);printf(M(F,0)=FM(F,1)=Fn);printf(please enter your string which is to be checked:n);lop:for(i=0;inputi-1!=n;i+)/输入0,1中的一个或多个字符组合。scanf(%c,&inputi);for(i=0;inputi-1!=n;i+)if(inputi!=0 &inputi!=1 &inputi!=n)printf(input error,enter again please:n);goto lop;printf(the status sequence is :n);a=realize(input);if(a=1)printf(nSo this string can be identifiedn);elseprintf(nthis string cann be identifiedn);printf(press error to exit the programn);getchar();3. 写出与该自动机相等价的正规式。 R = (0|1)0*1* 4. 根据正规式，构造一个由0,1构成的数字串，并作为输入，通过运行该自动机程序判断该字符串能否被该自动机所识别。 此处给出测试数据及运行结果。测试数据：0010测试结果：s a c f f教师