有穷状态自动机.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 <iostream>
using namespace std;

const int maxsize=10;

class DFA
{
private:
int M[maxsize][maxsize];
char Vn[maxsize],Vt[maxsize];
int VnNum,VtNum;

public:
DFA();
~DFA(){}
void print();
int move(char start,char s[]);
};
int DFA::move(char start,char s[])
{
char t[10];char next=start;
int left=0,right=0,i=0,j=0;
while(s[i]!='\0'){t[i]=s[i++];}
t[i]='\0';
while(t[0]!='\0')
{
left=0;right=0;
while(next!=Vn[left]){left++;}
while(t[0]!=Vt[right]){right++;}
if(M[left][right]!=-1&&left<VnNum&&right<VtNum)
{
next=Vn[M[left][right]];
cout<<"M("<<Vn[left]<<","<<Vt[right]<<")="<<next<<endl;
}
else return 0;
i=1;
while(t[i]!='\0'){t[i-1]=t[i++];}
t[i-1]='\0';
}
return 1;

}
DFA::DFA()
{
char grammar[maxsize],n[maxsize],t[maxsize];
int rule,left,right,final;
int i=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]!='\0')Vn[j+1]=n[j++];VnNum=j+1;
while(t[i]!='\0')Vt[i]=t[i++];VtNum=i;
for(i=0;i<VnNum;i++)
for(j=0;j<=VtNum;j++)M[i][j]=-1;
i=0;
while(i!=rule)
{
j=0;k=0;
cin>>grammar;
while(Vn[k]!=grammar[0])k++;
final=k;
while(grammar[j]!='\0')j++;
if(j==2)
{
k=0;
while(Vt[k]!=grammar[1])k++;
left=0;
right=k;
}
else
{
k=0;while(Vn[k]!=grammar[1])k++;left=k;
k=0;while(Vt[k]!=grammar[2])k++;right=k;
}
M[left][right]=final;
i++;
}
}
void DFA::print()
{
int i=0,j=0;
cout<<"DFA ({";
while(i!=VnNum){cout<<Vn[i++]<<",";}cout<<"},{";
while(j!=VtNum){cout<<Vt[j++]<<",";}cout<<"},M"<<endl;
cout<<"{"<<endl;
i=0;
while(i!=VnNum)
{ j=0;
while(j!=VtNum)
{
if(M[i][j]!=-1)
{
cout<<"M("<<Vn[i];
cout<<","<<Vt[j]<<")="<<Vn[M[i][j]]<<endl;
}
j++;
}
i++;
}
cout<<"},{"<<Vn[0]<<"},{"<<Vn[1]<<"}";
};
int main()
{
char t[10];
int i;
cout<<"------------------------------------------------"<<endl;
cout<<"---1.DFA构造,2.打印五元组,3.接受字符串,4.退出---";
cin>>i;DFA s;
while(i<=3)
{
//system("color 1e");
if(i==2)s.print();
if(i==3)
{cout<<"输入串";
cin>>t;if(s.move('S',t))cout<<"字符串"<<t<<"可以被该DFA所接收";
else cout<<"字符串"<<t<<"不能被该DFA所接收";}
cout<<"\n输入操作";
cin>>i;
}
system("pause");
}
实验结果：

实验总结：
通过本次实验，对有穷状态自动转换机有了更进一步的了解，掌握了其存储表示与正则文法的联系，并且通过对整个程序的阅读，知道了任意的正则文法如何以五元组的形式输出。能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合.通过本次实验，对有穷状态自动机的概念、其存储表示及其正则文法的联系，有了进一步的理解和认识，增强了动手能力和编程能力。

实验成绩

教师签名