不确定有穷自动机确定化编译原理实验报告

不确定有穷自动机的确定化编译原理实验报告 本文关键词：自动机，不确定，编译，原理，实验

不确定有穷自动机的确定化编译原理实验报告 本文简介：编译原理实验报告实验名称不确定有穷自动机的确定化实验时间_____2014年4月10日_______院系_______管理信息工程学院_______班级_______11计算机科学与技术____学号______201101020109____________姓名________姜高_________

不确定有穷自动机的确定化编译原理实验报告 本文内容：

编译原理实验报告

实验名称

不确定有穷自动机的确定化

实验时间_____

2014年4月10日_______

院

系_______管理信息工程学院_______

班

级_______11计算机科学与技术____

学

号______201101020109____________

姓

名________姜高__________________

1、

实验目的

不确定有穷自动机的确定化

2、

实验原理

用子集构造算法构造子集加入子集族中直到收敛（所有构造的子集都已存在于子集族）为止。如原来不确定有穷自动机的五元组形式为：M=（K，

For

每输入字母a

{

U:=closure(move(T,a));

不在S中

then

将U作为未被标记的子集加在S中

}

5.代码实现

#include

#define

MAXS

100

using

namespace

std;

string

NODE;

//结点集合

string

CHANGE;

//终结符集合

int

//NFA边数

struct

edge{

string

first;

string

change;

string

last;

};

struct

chan{

string

ltab;

string

jihe[MAXS];

};

void

kong(int

{

int

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=

+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<<“其中终态为：“<

}