有穷状态自动机.docx

《有穷状态自动机.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、西北师范大学计算机科学与工程学院学生实验报告学号111111专业计算机科学与技术班级技师(1)班姓名111课程名称编译原理课程类型实验实验名称有穷状态自动机实验目的：1，准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，为词法分析程序的自动构造寻找特殊的方法和工具；2，掌握了有穷状态自动转换机的概念；3，掌握DFA的存储表示；4，掌握DFA与正则文法的联系实验原理：1，一个确定的有穷状态自动机DFA是五元组（K,∑,M,S,F,）,其中，K是有穷非空的状态集合；∑是有穷非空的输入

2、字母表；M是从K×∑到K的映象。如果M（R,T）=Q，则输入字符为T时，当前状态R将转换到状态Q，Q成为下一当前状态；S是开始状态；F是非空的终止状态集合。输入任意的正则文法，输出相应的有穷状态自动机要求：识别有穷状态自动转换机是非确定的还是确定的，以相应的五元组形式输出。实验代码如下：实验源代码：#includeusingnamespacestd;constintmaxsize=10;classDFA{private:intM[maxsize][maxsize];charV

3、n[maxsize],Vt[maxsize];intVnNum,VtNum;public:DFA();~DFA(){}voidprint();intmove(charstart,chars[]);};intDFA::move(charstart,chars[]){chart[10];charnext=start;intleft=0,right=0,i=0,j=0;while(s[i]!=''){t[i]=s[i++];}t[i]='';while(t[0]!=''){left=0;r

4、ight=0;while(next!=Vn[left]){left++;}while(t[0]!=Vt[right]){right++;}if(M[left][right]!=-1&&left

5、1]='';}return1;}DFA::DFA(){chargrammar[maxsize],n[maxsize],t[maxsize];intrule,left,right,final;inti=0,j=0,k=0;cout<<"rule=";cin>>rule;cout<<"Vn";cin>>n;cout<<"Vt";cin>>t;cout<<"grammar";Vn[0]='S';j=0;while(n[j]!='')Vn[j+1]=n[j++];VnNum=j+1;while(

6、t[i]!='')Vt[i]=t[i++];VtNum=i;for(i=0;i>grammar;while(Vn[k]!=grammar[0])k++;final=k;while(grammar[j]!='')j++;if(j==2){k=0;while(Vt[k]!=grammar[1])k++;left=0;right=k;}else{k

7、=0;while(Vn[k]!=grammar[1])k++;left=k;k=0;while(Vt[k]!=grammar[2])k++;right=k;}M[left][right]=final;i++;}}voidDFA::print(){inti=0,j=0;cout<<"DFA({";while(i!=VnNum){cout<

8、cout<<"{"<