编译原理实验五:有穷自动机的确定化

实验五：有穷自动机的确定化

一：要求

1.输入： 非确定有限（穷）状态自动机。

2.输出： 确定化的有限（穷）状态自动

二：实验目的

1. 熟练掌握DFA及NFA的定义及有关概念。

2. 理解并掌握确定的有穷自动机的化简等算法。

三：实验原理

1.由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：

（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；

（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。 2. NFA确定化为DFA

同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。

下面介绍一种NFA的确定化算法，这种算法称为子集法：

（1） 若NFA的全部初态为S1，S2，…，Sn，则令DFA的初态为： S＝[S1，S2，…，Sn]，

其中方括号用来表示若干个状态构成的某一状态。

（2） 设DFA的状态集K中有一状态为[Si，Si+1，…，Sj]，若对某符号a∈∑，在NFA中有F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ }

则令F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ }为DFA的一个转换函数。若[ Si’，Si+1’，…，Sk‘ ]不在K中，则将其作为新的状态加入到K中。

（3） 重复第2步，直到K中不再有新的状态加入为止。

（4） 上面得到的所有状态构成DFA的状态集K，转换函数构成DFA的F，DFA的字母表仍然是NFA的字母表∑。

（5） DFA中凡是含有NFA终态的状态都是DFA的终态。 3. NFA确定化的实质是以原有状态集上的子集作为DFA上的一个状态，将原状态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。

四：数据结构与算法

struct edge{

string first;//边的初始结点

string condition;//边上的条件

string last;//边的终点

};

string closure(string a,edge *b)//求状态集合I的&-闭包，用&代替"空" string move(string collection,char ch,edge *b)//状态集合I的a弧转换 string sort(string t)//字符串排序

五：出错分析

1:缺少#include，会有很多错误。

2:在数据结构的定义之中，字符与字符串的差别，本次实验室字符串而不是字符

六：实验结果与分析

七：源代码

#include

#include

#include

using namespace std;

#define max 100

int n;//NFA的边数

vector value;

struct edge{

string first;//边的初始结点

string condition;//边上的条件

string last;//边的终点

};

string closure(string a,edge *b)//求状态集合I的&-闭包，用&代替"空"

{

int i,j;

for(i=0;i

{

for(j=0;j

{

if(b[j].first[0]==a[i]&&b[j].condition=="&")

{

a=a+b[j].last[0];

}

}

}

return a;

}

string move(string collection,char ch,edge *b)//状态集合I的a弧转换

{

int i,j;

string s="";

for(i=0;i

{

for(j=0;j

{

if(b[j].first[0]==collection[i]&&b[j].condition[0]==ch)

s=s+b[j].last;

}

}

return s;

}

string sort(string t)//字符串排序

{

int k,i,j;

char tt;

for(i=0;i

{

k=i;

for(j=i+1;j

{

if(t[j]

}

tt=t[k];t[k]=t[i];t[i]=tt;

}

return t;

}

void main()

{

int i,j,x=0,h,length,m,d=0;

string Condition;//边上的条件

string First,Last;//初态，终态，

string T[max],ss;

edge *b=new edge[max];

cout

cout

{

cin>>b[i].first;

if(b[i].first=="#")break;

else

cin>>b[i].condition>>b[i].last;

}

n=i;

cout

cin>>First>>Last;

cout

cin>>Condition;

s=s+b[j].last;

}

}

return s;

}

string sort(string t)//字符串排序

{

int k,i,j;

char tt;

for(i=0;i

{

k=i;

for(j=i+1;j

{

if(t[j]

}

tt=t[k];t[k]=t[i];t[i]=tt;

}

return t;

}

void main()

{

int i,j,x=0,h,length,m,d=0;

string Condition;//边上的条件

string First,Last;//初态，终态，

string T[max],ss;

edge *b=new edge[max];

cout

cout

{

cin>>b[i].first;

if(b[i].first=="#")break;

else

cin>>b[i].condition>>b[i].last;

}

n=i;

cout

cin>>First>>Last;

cout

cin>>Condition;

T[x]=closure(First,b);//字符串数组存储空闭包并排序

T[x]=sort(T[x]);

value.push_back(0);

i=0;

while(value[i]==0&&value.size())

{

value[i]=1;

for(j=0;j

{

ss="";

ss=move(T[i],Condition[j],b);

length=value.size();

for(h=0;h

{

if(T[h]==sort(closure(ss,b)))break;

}

if(h==length)

{

T[++x]=sort(closure(ss,b));

value.push_back(0);

}

}

i++;

}

edge *DFA=new edge[max];

for(i=0;i

{

for(j=0;j

{

DFA[d].first=T[i];

DFA[d].condition=Condition[j];

ss="";

ss=sort(closure(move(T[i],Condition[j],b),b));

for(m=0;m

if(ss==T[m])DFA[d++].last=T[m];

}

}

cout

{

for(m=0;m

{

if(DFA[i].first==T[m])cout

}

for(m=0;m

if(DFA[i].last==T[m])cout

cout

for(m=0;m

{

for(j=0;j

{

ss=T[m];

if(ss[j]==First[0])cout

}

}

cout

for(m=0;m

{

for(j=0;j

{

ss=T[m];

if(ss[j]==Last[0])cout

}

}

cout

system("pause");

}