不确定有穷自动机的确定化编译原理实验报告 本文关键词：自动机，不确定，编译，原理，实验
不确定有穷自动机的确定化编译原理实验报告 本文简介：编译原理实验报告实验名称不确定有穷自动机的确定化实验时间_____2014年4月10日_______院系_______管理信息工程学院_______班级_______11计算机科学与技术____学号______201101020109____________姓名________姜高_________
不确定有穷自动机的确定化编译原理实验报告 本文内容：
编译原理实验报告
实验名称
不确定有穷自动机的确定化
实验时间_____
2014年4月10日_______
院
系_______管理信息工程学院_______
班
级_______11计算机科学与技术____
学
号______201101020109____________
姓
名________姜高__________________
1、
实验目的
不确定有穷自动机的确定化
2、
实验原理
用子集构造算法构造子集加入子集族中直到收敛（所有构造的子集都已存在于子集族）为止。如原来不确定有穷自动机的五元组形式为：M=（K，
For
每输入字母a
DO
{
U:=closure(move(T,a));
If
U
不在S中
then
将U作为未被标记的子集加在S中
}
}
5.代码实现
#include
#include
#define
MAXS
100
using
namespace
std;
string
NODE;
//结点集合
string
CHANGE;
//终结符集合
int
N;
//NFA边数
struct
edge{
string
first;
string
change;
string
last;
};
struct
chan{
string
ltab;
string
jihe[MAXS];
};
void
kong(int
a)
{
int
i;
for(i=0;iNODE.find(a[i+1]))
{
b=a[i];
a[i]=a[i+1];
a[i+1]=b;
}
}
void
eclouse(char
c,string
for(k=0;khe.length())
he+=b[k].last;
eclouse(b[k].last[0],he,b);
}
}
}
void
move(chan
k=he.ltab.length();
l=he.jihe[m].length();
for(i=0;ihe.jihe[m].length())
he.jihe[m]+=b[j].last[0];
for(i=0;ihe.jihe[m].length())
he.jihe[m]+=b[j].last[0];
}
//输出
void
outputfa(int
len,int
h,chant)
{
int
i,j,m;
cout>b[i].first;
if(b[i].first==“#“)
break;
cin>>b[i].change>>b[i].last;
}
N=i;
/*for(j=0;jNODE.length())
NODE+=b[i].first;
if(NODE.find(b[i].last)>NODE.length())
NODE+=b[i].last;
if((CHANGE.find(b[i].change)>CHANGE.length())
}
len=CHANGE.length();
cout>endnode;
for(i=0;iNODE.length())
{
cout“;
move(t[i],k,b);
//求move(I,a)
//coutednode.length())
d[0]+=NODE[i];
endnode=ednode;
cout< outputfa(len,h,t); //输出DFA cout<<“其中终态为：“< //DFA最小化 m=2; sta.erase(); flag=0; for(i=0;i { //cout<<“d[“< for(k=0;k { //cout<<“I“< y=m; for(j=0;j { for(n=0;n { if(d[n].find(t[NODE.find(d[i][j])].jihe[k]) ) { if(t[NODE.find(d[i][j])].jihe[k].length()==0) x=m; else x=n; if(!sta.length()) { sta+=x+48; } else if(sta[0]!=x+48) { d[m]+=d[i][j]; flag=1; d[i].erase(j,1); //cout< j--; } break; //跳出n } }//n }//j if(flag) { m++; flag=0; } //cout<<“sta=“< sta.erase(); }//k }//i cout< for(i=0;i cout<<“{“< “; cout< //状态重新命名 chanmd=new chan[m]; NODE.erase(); cout< for(i=0;i { md[i].ltab= A +i; NODE+=md[i].ltab; cout<<“{“< } for(i=0;i for(k=0;k for(j=0;j { if(d[i][0]==t[j].ltab[0]) { for(n=0;n { if(!t[j].jihe[k].length()) break; else if(d[n].find(t[j].jihe[k]) { md[i].jihe[k]=md[n].ltab; break; } } break; } } ednode.erase(); for(i=0;i for(j=0;j if(d[i].find(endnode[j]) endnode=ednode; cout< outputfa(len,m,md); cout<<“其中终态为：“< }