有穷状态自动机.docx

西北师范大学计算机科学与工程学院学生实验报告学号111111专业计算机科学与技术班级技师(1)班姓名111课程名称编译原理课程类型 实验实验名称 有穷状态自动机实验目的：1， 准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，为词法分析程序的自动构造寻找特殊的方法和工具；2， 掌握了有穷状态自动转换机的概念；3， 掌握DFA的存储表示；4， 掌握DFA与正则文法的联系实验原理：1， 一个确定的有穷状态自动机DFA是五元组（K,M,S,F,）,其中，K是有穷非空的状态集合；是有穷非空的输入字母表；M是从K到K的映象。如果M（R,T）=Q，则输入字符为T时，当前状态R将转换到状态Q，Q成为下一当前状态；S是开始状态；F是非空的终止状态集合。输入任意的正则文法，输出相应的有穷状态自动机要求：识别有穷状态自动转换机是非确定的还是确定的，以相应的五元组形式输出。实验代码如下：实验源代码：#include using namespace std;const int maxsize=10;class DFA private: int Mmaxsizemaxsize; char Vnmaxsize,Vtmaxsize; int VnNum,VtNum; public: DFA(); DFA() void print(); int move(char start,char s);int DFA:move(char start,char s) char t10;char next=start; int left=0,right=0,i=0,j=0; while(si!=0)ti=si+; ti=0; while(t0!=0) left=0;right=0; while(next!=Vnleft)left+; while(t0!=Vtright)right+; if(Mleftright!=-1&leftVnNum&rightVtNum) next=VnMleftright; coutM(Vnleft,Vtright)=nextendl; else return 0; i=1; while(ti!=0)ti-1=ti+; ti-1=0; return 1; DFA:DFA() char grammarmaxsize,nmaxsize,tmaxsize; int rule,left,right,final; int i=0,j=0,k=0; coutrule; coutn; coutt; coutgrammar; Vn0=S; j=0; while(nj!=0)Vnj+1=nj+;VnNum=j+1; while(ti!=0)Vti=ti+;VtNum=i; for(i=0;iVnNum;i+) for(j=0;jgrammar; while(Vnk!=grammar0)k+; final=k; while(grammarj!=0)j+; if(j=2) k=0; while(Vtk!=grammar1)k+; left=0; right=k; else k=0;while(Vnk!=grammar1)k+;left=k; k=0;while(Vtk!=grammar2)k+;right=k; Mleftright=final; i+; void DFA:print() int i=0,j=0; coutDFA (; while(i!=VnNum)coutVni+,;cout,; while(j!=VtNum)coutVtj+,;cout,Mendl; coutendl; i=0; while(i!=VnNum) j=0; while(j!=VtNum) if(Mij!=-1) coutM(Vni; cout,Vtj)=VnMijendl; j+; i+; cout,Vn0,Vn1;int main() char t10; int i; cout-endl; couti;DFA s; while(i=3) /system(color 1e); if(i=2)s.print(); if(i=3) coutt;if(s.move(S,t)cout字符串t可以被该DFA所接收; else cout字符串t不能被该DFA所接收; couti; system(pause);实验结果：实验总结：通过本次实验，对有穷状态自动转换机有了更进一步的了解，掌握了其存储表示与正则文法的联系，并且通过对整个程序的阅读，知道了任意的正则文法如何以五元组的形式输出。能准