首页 > 代码库 > 有穷自动机的构造与识别
有穷自动机的构造与识别
一、实验目标
1、掌握有穷状态自动机的概念;
2、掌握有穷状态自动机的存储及表示方法;
3、掌握有穷状态自动机与正则式之间的关系。
二、实验要求
1、输入正规式;
2、构造该正规式的有穷状态自动机;
3. 以五元组形式输出。
三、实验算法
四、实验程序
1 #include<string.h> 2 #include<stdio.h> 3 #include<stdlib.h> 4 int main() 5 { 6 char p[30][30]; 7 char q[30][30]; 8 int line=0; 9 int n; 10 int i,j; 11 int count=0; 12 int k,t=0; 13 int flag=0; 14 int l,m=0; 15 char VN[30]={‘\0‘}; 16 char VT[30]={‘\0‘}; 17 printf("规则数:"); 18 scanf("%d",&n); 19 line=n; 20 for(i=0;i<30;i++) 21 for(j=0;j<30;j++) 22 { 23 p[i][j]=‘\0‘; 24 q[i][j]=‘\0‘; 25 } 26 printf("请输入文法:\n"); 27 for(i=0;i<line;i++) 28 { 29 scanf("%s",p[i]); 30 } 31 32 l=0; 33 m=0; 34 for(i=0;i<line;i++) 35 { 36 for(j=0;j<30&&(p[i][j]!=‘\0‘);j++) 37 { 38 39 if(p[i][j]<=‘z‘&&p[i][j]>=‘a‘||(p[i][j]<=‘9‘&&p[i][j]>=‘0‘)) 40 { 41 flag=0; 42 for(t=0;VN[t]!=‘\0‘;t++) 43 { 44 if(VN[t]==p[i][j]) 45 { 46 flag=1;break; 47 } 48 } 49 if(flag==0) 50 { 51 VN[l]=p[i][j]; 52 l++; 53 } 54 } 55 56 if(p[i][j]<=‘Z‘&&p[i][j]>=‘A‘) 57 { 58 flag=0; 59 for(t=0;t<30&&(VT[t]!=‘\0‘);t++) 60 { 61 if(VT[t]==p[i][j]) 62 { 63 flag=1; 64 break; 65 } 66 } 67 if(flag==0) 68 { 69 VT[m]=p[i][j]; 70 m++; 71 } 72 } 73 } 74 } 75 76 count=0; 77 k=0; 78 for(i=0;i<line;i++) 79 { 80 for(j=4;j<30&&(p[i][j]!=‘\0‘);j++) 81 { 82 if((p[i][j]<=‘z‘&&p[i][j]>=‘a‘)||(p[i][j]<=‘Z‘&&p[i][j]>=‘A‘)||(p[i][j]<=‘9‘&&p[i][j]>=‘0‘)) 83 { 84 q[count][k]=p[i][j]; 85 k++; 86 } 87 else 88 { 89 count++; 90 k=0; 91 } 92 } 93 count++; 94 k=0; 95 } 96 flag=0; 97 for(i=0;i<count;i++) 98 { 99 for(j=i+1;j<count;j++) 100 { 101 if(strcmp(q[i],q[j])==0) 102 { 103 flag=1; 104 break; 105 } 106 } 107 } 108 if(flag==1) 109 { 110 printf("是非确定的有穷状态自动机,即NFA\n\n"); 111 printf("构造的有穷状态自动机为:\n"); 112 printf("NFA N=(K,E(总和的意思),M,{S},{Z})\n"); 113 } 114 else 115 { 116 printf("是确定的有穷状态自动机,即DFA\n\n\n"); 117 printf("构造的有穷状态自动机为:\n"); 118 printf("DFA N=(K,E(总和的意思),M,{S},{Z})\n"); 119 } 120 printf("其中,\nK={S"); 121 for(i=0;i<30&&(VT!=‘\0‘);i++) 122 { 123 printf(",%c",VT[i]); 124 } 125 printf("}\n"); 126 printf("E={"); 127 for(i=0;i<30&&(VN[i]!=‘\0‘);i++) 128 { 129 printf("%c ",VN[i]); 130 } 131 printf("}\n"); 132 133 k=0; 134 count=0; 135 for(i=0;i<line;i++) 136 { 137 j=4; 138 while(p[i][j]!=‘\0‘) 139 { 140 if(k<4) 141 { 142 q[count][k]=p[i][k]; 143 k++; 144 } 145 else 146 { 147 if((p[i][j]<=‘z‘&&p[i][j]>=‘a‘)||(p[i][j]<=‘Z‘&&p[i][j]>=‘A‘)||(p[i][j]<=‘9‘&&p[i][j]>=‘0‘)) 148 { 149 q[count][k]=p[i][j]; 150 k++; 151 j++; 152 } 153 if(p[i][j]==‘l‘) 154 { 155 count++; 156 k=0; 157 j++; 158 } 159 } 160 } 161 count++; 162 k=0; 163 } 164 printf("\n"); 165 166 printf("M:\n"); 167 l=0; 168 while(VN[l]!=‘\0‘) 169 { 170 printf("M(S,%c)={",VN[l]); 171 for(i=0;i<30;i++) 172 { 173 for(j=4;j<30&&(q[i][j]!=‘\0‘);j++) 174 { 175 if(VN[l]==q[i][j]&&(q[i][j+1]==‘\0‘)&&(q[i][j-1]==‘=‘)) 176 printf("%c",q[i][0]); 177 } 178 } 179 printf("}\t"); 180 l++; 181 } 182 printf("\n"); 183 l=0;k=0; 184 while(VT[k]!=‘\0‘) 185 { 186 l=0; 187 while(VN[l]!=‘\0‘) 188 { 189 printf("M(%c,%c)={",VT[k],VN[l]); 190 for(i=0;i<30;i++) 191 { 192 for(j=4;j<30&&(q[i][j]!=‘\0‘);j++) 193 { 194 if(VT[k]==q[i][j]&&VN[l]==q[i][j+1]) 195 printf("%c",q[i][0]); 196 } 197 } 198 printf("}\t"); 199 l++; 200 } 201 k++; 202 printf("\n"); 203 } 204 system("pause"); 205 }
五、运行结果
六、心得体会
通过对有穷自动机的构造与识别的学习后,让我掌握了正规文法式R构造NFA的方法。
但是,还有很多不懂的知识。希望日后能过慢慢理解并掌握。
有穷自动机的构造与识别
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。