首页 > 代码库 > 实验三 有限自动机的构造与识别
实验三 有限自动机的构造与识别
实验三 有限自动机的构造与识别
一、实验目标
1、掌握有穷状态自动机的概念;
2、掌握有穷状态自动机的存储及表示方法;
3、掌握有穷状态自动机与正则式之间的关系。
二、实验要求
1、输入正规式;
2、构造该正规式的有穷状态自动机;
3. 以五元组形式输出。
#include<stdio.h> #include <string.h> #define ok 1 #define error 0 #define N 50 int iCurrentState=0; //初态以1开始 int iPreState=0; int iForkState=0; int iLastForkState=0; int iMaxState=0; char x[N]; //输入的正规式字符串 char cCharSet[N]; //字符集 int iStateMatrix[N][N]; //状态转换矩阵 int vString()//把字符串读入一个缓冲区中 { scanf("%s",x); return ok; } int vProcessString()//对字符串进行预处理,去掉字符串里面的对分析不产生影响 { int i=0; while(x[i]!=‘\0‘) { if(x[i]==‘*‘) { int j=i+1; while(x[j-1]!=‘\0‘) { x[j-1]=x[j++]; } } i++; } return ok; } void ConstructMatrix(char cChar,int istate)//构造状态转换矩阵 { int i; for(i=0;cCharSet[i]!=‘\0‘;i++) if(cChar==cCharSet[i]) break; cCharSet[i]=cChar; iStateMatrix[iPreState][i]=istate; } void vAanalyString()//对字符串进行从左到右的分析与处理 { int i=0; for(i=0;x[i]!=0;i++) { if(x[i]==‘(‘) //NFA出现开始分叉情况 { int iTheFirstl=0; int iCharNumBeforl=0; iForkState=iCurrentState; while(x[i]!=‘)‘) { i++; if(isalpha(x[i])) { if(x[i+1]==‘)‘) iCurrentState=iLastForkState; else iCurrentState++; iCharNumBeforl++; ConstructMatrix(x[i],iCurrentState); iPreState=iCurrentState; if(iCurrentState>iMaxState) iMaxState=iCurrentState; } if(x[i]==‘|‘) { iPreState=iForkState; if(iTheFirstl==0) { iLastForkState=iCurrentState; iTheFirstl++; } if(iCharNumBeforl==1&&x[i+2]==‘|‘) iCurrentState=iForkState; iCharNumBeforl=0; } if(x[i]==‘)‘) { iPreState=iForkState=iLastForkState; iCurrentState=iMaxState; } } } else { if(isalpha(x[i])) { iCurrentState++; ConstructMatrix(x[i],iCurrentState); iPreState=iCurrentState; if(iCurrentState>iMaxState) iMaxState=iCurrentState; } } } } void vPrintfF()//输出f函数 { int icCharSetPointer; int iPreStatePointer; for(iPreStatePointer=0;iPreStatePointer<N;iPreStatePointer++) for(icCharSetPointer=0;icCharSetPointer<N;icCharSetPointer++) if(iStateMatrix[iPreStatePointer][icCharSetPointer]>0) printf("f(%d,%c)=%d\n",iPreStatePointer,cCharSet[icCharSetPointer],iStateMatrix[iPreStatePointer][icCharSetPointer]); } void vPrintfNFA()//输出NFA { int iStateNumble; int i=0; printf("\nNFA的形式为:(K,$,f,S,Z)\n\n以下为NFA的具体集合内容:\n"); printf("\n初态集S为:{0}\n\n"); printf("终态集Z为:{%d}\n",iMaxState); printf("\n字符集f为:{"); while(cCharSet[i]!=0) if(cCharSet[i+1]==0) printf("%c",cCharSet[i++]); else printf("%c,",cCharSet[i++]); printf("}\n"); printf("\n状态集K为:{"); for (i=0;i<=iMaxState;i++) { if(i==iMaxState) printf("%d",i); else printf("%d,",i); } printf("}\n\n"); vPrintfF(); } void main() { printf("请输入正规式:"); vString(); vProcessString(); vAanalyString(); vPrintfNFA(); printf("\n"); }
运行:
实验三 有限自动机的构造与识别
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。