首页 > 代码库 > 实验三有限自动机的构造与识别
实验三有限自动机的构造与识别
#include<stdio.h> #include <ctype.h> #define ok 1 #define error 0 #define MAXREGLUARLONG 40 #define MAXSTATELONG 40 #define MAXCAHRSLONG 40 typedef int state; int iCurrentState=0; //初态以1开始 int iPreState=0; int iLastForkState=0; int iForkState=0; int iMaxState=0; char cRegluarSting[MAXREGLUARLONG]; //输入的正规式字符串 char cCharSet[MAXCAHRSLONG]; //字符集 int iStateMatrix[MAXSTATELONG][MAXCAHRSLONG]; //状态转换矩阵 state vStoreRegluarSting()//把字符串读入一个缓冲区中 { scanf("%s",cRegluarSting); return ok; } state vPreProcessRegluarSting() //对字符串进行预处理,去掉字符串里面的对分析不产生影响 { int i=0; while(cRegluarSting[i]!=‘\0‘) { if(cRegluarSting[i]==‘*‘) { int j=i+1; while(cRegluarSting[j-1]!=‘\0‘) { cRegluarSting[j-1]=cRegluarSting[j++]; } } i++; } return ok; } void vConstructStateMatrix(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 vAanalyseRegluarSting()//对字符串进行从左到右的分析与处理 { int i=0; for(i=0;cRegluarSting[i]!=0;i++) { if(cRegluarSting[i]==‘(‘) //NFA出现开始分叉情况 { int iTheFirstl=0; int iCharNumBeforl=0; iForkState=iCurrentState; while(cRegluarSting[i]!=‘)‘) { i++; if(isalpha(cRegluarSting[i])) { if(cRegluarSting[i+1]==‘)‘) iCurrentState=iLastForkState; else iCurrentState++; iCharNumBeforl++; vConstructStateMatrix(cRegluarSting[i],iCurrentState); iPreState=iCurrentState; if(iCurrentState>iMaxState) iMaxState=iCurrentState; } if(cRegluarSting[i]==‘|‘) { iPreState=iForkState; if(iTheFirstl==0) { iLastForkState=iCurrentState; iTheFirstl++; } if(iCharNumBeforl==1&&cRegluarSting[i+2]==‘|‘) iCurrentState=iForkState; iCharNumBeforl=0; } if(cRegluarSting[i]==‘)‘) { iPreState=iForkState=iLastForkState; iCurrentState=iMaxState; } } } else { if(isalpha(cRegluarSting[i])) { iCurrentState++; vConstructStateMatrix(cRegluarSting[i],iCurrentState); iPreState=iCurrentState; if(iCurrentState>iMaxState) iMaxState=iCurrentState; } } } } void vPrintfStateProjectFunction() { int icCharSetPointer; int iPreStatePointer; for (iPreStatePointer=0;iPreStatePointer<MAXSTATELONG;iPreStatePointer++) for(icCharSetPointer=0;icCharSetPointer<MAXSTATELONG;icCharSetPointer++) if(iStateMatrix[iPreStatePointer][icCharSetPointer]>0) printf("&(%d,%c)=%d\n",iPreStatePointer,cCharSet[icCharSetPointer],iStateMatrix[iPreStatePointer][icCharSetPointer]); } void vPrintfNfa()//输出NFA { int iStateNumble; int i=0; printf("NFA的形式为:(S,$,&,S0,F)\n\n以下为NFA的具体集合内容:\n\n"); printf("字符集$为:{"); while(cCharSet[i]!=0) if(cCharSet[i+1]==0) printf("%c",cCharSet[i++]); else printf("%c,",cCharSet[i++]); printf("}\n"); printf("\n状态集S为:{"); for (i=0;i<=iMaxState;i++) { if(i==iMaxState) printf("%d",i); else printf("%d,",i); } printf("}\n\n"); vPrintfStateProjectFunction(); printf("\n初态集S0为:{0}\n\n"); printf("终态集F为:{%d}",iMaxState); } void main() { vStoreRegluarSting(); vPreProcessRegluarSting(); vAanalyseRegluarSting(); vPrintfNfa(); }
实验三有限自动机的构造与识别
一、 实验目的
1、掌握有穷状态自动机的概念;
2、掌握有穷状态自动机的存储及表示方法;
3、掌握有穷状态自动机与正则式之间的关系。
实验内容和要求
1、输入正规式;
2、构造该正规式的有穷状态自动机;
3. 以五元组形式输出。
练习:
2 (a|b)*abb
2 l(l|d)*
2 1(1010*|1(010)*1)*0
二、 实验方法、步骤及结果测试
- 1. 运行结果及分析
一般必须配运行结果截图,结果是否符合预期及其分析。
(截图需根据实际,截取有代表性的测试例子)
3
4.
三、 实验总结
实验三有限自动机的构造与识别
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。