形式语言与自动机确定的有穷状态自动机..docx

设计题目构造一个确定有穷状态自动机DFA，它接受的语言为{x|x∈{0，1}*，且当把x看成二进制数时，x模2与0同余}。运行环境硬件：Haier A60 Notebook，Celeron M 1.86GHz\512MB\250GB软件：Windows xp professional 5.1，visual C++ 6.0算法设计的思想输入一段0、1字符语言，把此语言看成是一个二进制数x，即求x要能否被2整除。当二进制数x的位数向右不断增加时，它的值（换算成十进制）的增加很有规律：x0的值等于2x，x1的值等于2x+1，据此规律，可实现满足要求的算法。算法的流程图简单的程序流程图：算法分析设计在visual C++ 6.0中， 新建一个win32 Console Application的应用程序，工程名为ModTwoThree,新建类ModTwo,用于编写模二运算的算法，在其构造函数ModTwo（）中，实现具体功能。定义两个字符数组ch[100]和a[100],其中ch[100]用于存储从屏幕控制台输入的语言，即0、1字符串；a[100]用于存储程序当前正在处理的字符串。输入语言后首先利用一个for循环语句判断ch中是否存在非0、1安符，若存在，则显示语言不满足自动机识别条件，无法执行算法。若不存在非0、1安符，判断接受字符，若为0，二进制对应的十进制数为n=2*n+0,同时执行a[i]=ch[i]，使安符数组a始终表示当前处理的二进制字符串，执行if(n%2==0)，判断结果，同时输出a；若接受字符为1，二进制对应的十进制数为n=2*n+0,同时执行a[i]=ch[i]，使安符数组a始终表示当前处理的二进制字符串，执行n%2==0，判断结果，同时输出a。同时发现，此程序能够很好的移植用于二进制模三、模四、模五等二进制除模运算，只需将判断语句if(n%2==0)改为if(n%3==0)等即可。源代码：进制模二运算：ModTwo::ModTwo(){int i=0,j=0,n=0;char ch[100],a[100]=,c;cout请输入0 1字符串的语言：endl;do{scanf(%c,ch[i]);c=ch[i];i++;}while(c!=\n);ch[i]=\0;cout你所输入的语言：endl;i=0;while(ch[i]!=\0){printf(%c,ch[i]);i++;}j=i;for(i=0;ij-1;i++){if(ch[i]!=0ch[i]!=1){cout输入语言中包括非0、1字符，无法被自动机所接受!!!endl;break;}else if(ch[i]==0)n=2*n+0;else if(ch[i]==1)n=2*n+1;a[i]=ch[i];if(n%2==0)couta能被2整除!endl;else if(n%2==1)couta不能被2整除!endl;}}二进制模三运算：ModThree::ModThree(){int i=0,j=0,n=0;char ch[100],a[100]=,c;cout请输入0 1字符串的语言：endl;do{scanf(%c,ch[i]);c=ch[i];i++;}while(c!=\n);ch[i]=\0;cout你所输入的语言：endl;i=0;while(ch[i]!=\0){printf(%c,ch[i]);i++;}j=i;for(i=0;ij-1;i++){if(ch[i]!=0ch[i]!=1){cout输入语言中包括非0、1字符，无法被自动机所接受!!!endl;break;}else if(ch[i]==0)n=2*n+0;else if(ch[i]==1)n=2*n+1;a[i]=ch[i];if(n%3==0)couta能被3整除!endl;else if(n%3==1)couta不能被3整除!endl;else if(n%3==2)couta不能被3整除!endl;}}收获及体会?运行结果如下：