有穷自动机的构造与识别 238

一、实验目标
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 }

View Code

五、运行结果

六、心得体会

通过对有穷自动机的构造与识别的学习后，让我掌握了正规文法式R构造NFA的方法。

但是，还有很多不懂的知识。希望日后能过慢慢理解并掌握。