一、实验目标
1、掌握有穷状态自动机的概念；
2、掌握有穷状态自动机的存储及表示方法；
3、掌握有穷状态自动机与正则式之间的关系。
二、实验要求
1、输入正规式；
2、构造该正规式的有穷状态自动机；
3. 以五元组形式输出。
三、算法
参见教材
练习：
² (a|b)*abb
² l(l|d)*
² 1(1010*|1(010)*1)*0
四、完成算法设计、编码和调试工作，完成实验报告。
#include <string.h>
#include <stdio.h>
#include <stdlib.h> int main() { char p[30][30]; //存放文法 char q[30][30]; int line=0; int n; int i,j; int count=0; int k,t=0; int flag=0; int l,m=0; char VN[30] = {'\0'}; //存放非终结符号 char VT[30] = {'\0'}; //存放终结符号 printf("\t请输入规则个数："); scanf("%d",&n); line = n; for(i = 0; i < 30; i++)//给字符串数组p、q全部赋值为'\0' for(j=0;j<30;j++){p[i][j]='\0';q[i][j]='\0';} printf("\t请输入文法:\n"); for(i = 0; i < line; i++) {printf("\t");scanf("\t%s",p[i]);} //把字符分为终结符号合非终结符号 l=0;m=0; for(i = 0;i < line; i++) { for(j = 0;j < 30&&(p[i][j] != '\0');j++) { // 非终结符号放入数组VN中 if((p[i][j]<='z' && p[i][j]>='a')||(p[i][j]<='9' && p[i][j]>='0')) { flag = 0; for(t=0; VN[t] != '\0';t++){if(VN[t] == p[i][j]){flag = 1;break;}} if(flag == 0){VN[l] = p[i][j];l++;} } // 终结符号放入数组VT中 if(p[i][j]<='Z' && p[i][j]>='A') { flag = 0; for(t = 0; t<30&&(VT[t] != '\0'); t++){if(VT[t] == p[i][j]){flag = 1;break;}} if(flag==0){VT[m] = p[i][j];m++;} } } //把规则右部分分离放入数组q中 count = 0; k =0; for(i = 0;i < line;i++) { for(j = 4;j < 30 && (p[i][j] != '\0');j++) { 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')){q[count][k] = p[i][j];k++;} else{count++;k =0;} } count++;k=0; } //判断是确定的还是非确定的有穷状态自动并进行前半部分打印 //判断依据：q数组中每一行字符串是否相同 flag = 0; for(i=0;i<count;i++) { for(j=i+1;j<count;j++) { if(strcmp(q[i],q[j])==0){flag=1;break;} if(flag==0){VT[m]=p[i][j];m++;} } } } // 把规则右部分分离放入数组 q 中 count=0; k=0; for(i=0;i<line;i++) { for(j=4;j<30&&(p[i][j]!='\0');j++) { 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')){q[count][k]=p[i][j];k++;} else{count++;k=0;} } count++;k=0; } // 判断是确定的还是非确定的有穷状态自动机并进行前半部分打印 // 判断依据q 数组中每一行字符串是否相同 flag=0; for(i=0;i<count;i++) { for(j=i+1;j<count;j++) { if(strcmp(q[i],q[j])==0) {flag=1;break;} } } if(flag==1){printf("\t是非确定的有穷状态自动机，即 NFA\n\n"); printf("\t构造的有穷状态自动机为： \n"); printf("\tNFA N= （ K ，∑， M ， {S} ， {Z} ） \n");} else{printf("\t是确定的有穷状态自动机，即 DFA\n\n\n"); printf("\t构造的有穷状态自动机为： \n"); printf("\tDFA D= （ K ，∑， M ， {S} ， {Z} ） \n");} printf("\t其中:\n\tK={S"); for(i=0;i<30&&(VT[i]!='\0');i++){printf(" ， %c",VT[i]);} printf("}\n");printf("\t∑ ={"); for(i=0;i<30&&(VN[i]!='\0');i++){printf("%c ",VN[i]);} printf("}\n");k=0;count=0; for(i=0;i<line;i++) { j=4;while(p[i][j]!='\0') { if(k<4){q[count][k]=p[i][k];k++;} else{ 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')){q[count][k]=p[i][j];k++;j++;} if(p[i][j]=='|'){count++;k=0;j++;} } } count++;k=0; } printf("\n");printf("\tM:\n");l=0; while(VN[l]!='\0') { printf("\tM(S,%c)={",VN[l]); for(i=0;i<30;i++) { for(j=4;j<30&&(q[i][j]!='\0');j++) { if(VN[l]==q[i][j]&&(q[i][j+1]=='\0')&&(q[i][j-1]=='=')) printf("%c",q[i][0]); } } printf("}\t");l++; } printf("\n"); l=0; k=0; while(VT[k]!='\0') { l=0; while(VN[l]!='\0') { printf("\tM(%c,%c)={",VT[k],VN[l]); for(i=0;i<30;i++) { for(j=4;j<30&&(q[i][j]!='\0');j++) { if(VT[k]==q[i][j]&&VN[l]==q[i][j+1]) printf("%c",q[i][0]); } } printf("}\t");l++; } k++;printf("\n"); } system("pause"); }