NFA确定化

1．实验目的

设计并实现将NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。该算法也是构造LR分析器的基础。

2．实验要求

设计并实现计算状态集合I的ε闭包的算法ε_Closure(I)和转换函数Move(I,a)，并在此基础上实现子集构造算法Subset_Construction。利用该从NFA到DFA的转换程序Subset_Construction，任意输入一个NFA N=（S,Σ,δ,s0,F），输出一个接收同一语言的DFA M=（S’,Σ,δ’,s0’,F’）。

3．实验内容

(1) 令I是NFA N的状态集S的一个子集，I的ε闭包的ε_Closure(I)构造规则如下：

(a) 若s∈I，则s∈ε_Closure(I)；

(b) 若s∈ε_Closure(I)且δ(s, ε)=s’而s’ ∉ε_Closure(I) ，则s’∈ε_Closure(I)

根据上面的规则，下面给出了一个计算I的ε闭包的算法ε_Closure(I)。

SET S;

SETε_Closure(input)

精选

SET *input;

{

S=input; /* 初始化 */

push(); /* 把输入状态集中的全部状态压入栈中while(栈非空){

Nfa_state i;

pop(); /* 把栈顶元素弹出并送入i */

if(存在δ(i, ε)=j)

if(j不在S中) {

把i加到S中;

把j压入栈中;

}

}

精选

*/

return S; /* 返回ε_Closure(input)集合 */

}

完成上述算法的设计。

(2) 令I是NFA N的状态集S的一个子集，a∈Σ, 转换函数Move(I,a)定义为：

Move(I,a)= ε_Closure(J)

其中，J={s’|s∈I且δ(s,a)=s’}

转换函数Move(I,a)的设计通过调用ε_Closure(input)实现，完成该函数的设计。

(3) 从NFA N构造一个与其等价的DFA M的子集构造算法，就是要为DFA M构造

状态转换表Trans，表中的每个状态是NFA N状态的集合，DFA M将“并行”地模拟NFA N面对输入符号串所有可能的移动。下面给出了子集构造算法Subset_Construction的框架，请完成其设计过程。

有关数据结构：

States[] 是一个M的数组，每个状态有两个域，set域存放N的状态集合，flg域为一标识。

Trans[] 是M的转移矩阵（输入字母表Σ元素个数×最大状态数），Trans[i][a]=下一状态。

精选

i M的当前状态号

a 输入符号，a∈Σ

Nstates[] M的下一新状态号

S 定义M的一个状态的N的状态集

初始化：

States[0].set=ε_Closure({N的初态})

States[0].flg=FALSE

Nstates=1

i=0

S=Ф

Trans初始化为无状态’-’

while(States[i]的flg为FALSE){

States[i].flg=TRUE;

精选

for(每个输入符号a∈Σ){

S=ε_Closure(Move(States[i].set,a));

if(S非空)

if(States中没有set域等于 S的状态){

States[Nstates].set=S;

States[Nstates].flg=FALSE;

Trans[i][a]= Nstates++;

}

else

Trans[i][a]= States中一个set域为S的下标;

}

}

此算法的输出M主要由Trans矩阵描述，其中省略了每个状态是否为终态的描述，应加以完善。

精选

4．实验程序;

#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;icout<<' ';

}

//排序

void paixu(string &a)

{

精选

int i,j;

char b;

for(j=0;jfor(i=0;iif(NODE.find(a[i])>NODE.find(a[i+1]))

{

b=a[i];

a[i]=a[i+1];

a[i+1]=b;

}

}

void eclouse(char c,string &he,edge b[])

{

精选

int k;

for(k=0;k{

if(c==b[k].first[0])

if(b[k].change==\"*\")

{

if(he.find(b[k].last)>he.length())

he+=b[k].last;

eclouse(b[k].last[0],he,b);

}

}

}

void move(chan &he,int m,edge b[])

精选

{

int i,j,k,l;

k=he.ltab.length();

l=he.jihe[m].length();

for(i=0;ifor(j=0;jif((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0]))

if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())

he.jihe[m]+=b[j].last[0];

for(i=0;ifor(j=0;jif((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0]))

if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())

精选

he.jihe[m]+=b[j].last[0];

}

//输出

void outputfa(int len,int h,chan *t)

{

int i,j,m;

cout<<\" I \";

for(i=0;icout<<'I'<cout<for(i=0;i{

cout<<' '<精选

m=t[i].ltab.length();

for(j=0;j{

kong(8-m);

m=t[i].jihe[j].length();

cout<}

cout<}

}

void main()

{

edge *b=new edge[MAXS];

精选

int i,j,k,m,n,h,x,y,len;

bool flag;

string jh[MAXS],endnode,ednode,sta;

cout<<\"请输入NFA各边信息（起点 条件[空为*] 终点），以#结束：\"<for(i=0;i{

cin>>b[i].first;

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

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

}

N=i;

/*for(j=0;jcout<精选

for(i=0;i{

if(NODE.find(b[i].first)>NODE.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())&&(b[i].change!=\"*\"))

CHANGE+=b[i].change;

}

len=CHANGE.length();

cout<<\"结点中属于终态的是：\"<cin>>endnode;

for(i=0;i精选

if(NODE.find(endnode[i])>NODE.length())

{

cout<<\"所输终态不在集合中，错误！\"<return;

}

//cout<<\"endnode=\"<chan *t=new chan[MAXS];

t[0].ltab=b[0].first;

h=1;

eclouse(b[0].first[0],t[0].ltab,b); //求e-clouse

//cout<for(i=0;i{

精选

for(j=0;jfor(m=0;meclouse(t[i].ltab[j],t[i].jihe[m],b); //求e-clouse

for(k=0;k{

//cout<\";

move(t[i],k,b); //求move(I,a)

//cout<for(j=0;jeclouse(t[i].jihe[k][j],t[i].jihe[k],b); //求e-clouse

}

for(j=0;j{

精选

paixu(t[i].jihe[j]); //对集合排序以便比较

for(k=0;k{

flag=operator==(t[k].ltab,t[i].jihe[j]);

if(flag)

break;

}

if(!flag&&t[i].jihe[j].length())

t[h++].ltab=t[i].jihe[j];

}

}

cout<outputfa(len,h,t); //输出状态转换矩阵

精选

//状态重新命名

string *d=new string[h];

NODE.erase();

cout<for(i=0;i{

sta=t[i].ltab;

t[i].ltab.erase();

t[i].ltab='A'+i;

NODE+=t[i].ltab;

cout<<'{'<for(j=0;jif(sta.find(endnode[j])精选

d[1]=ednode+=t[i].ltab;

for(k=0;kfor(m=0;mif(sta==t[k].jihe[m])

t[k].jihe[m]=t[i].ltab;

}

for(i=0;iif(ednode.find(NODE[i])>ednode.length())

d[0]+=NODE[i];

endnode=ednode;

cout<outputfa(len,h,t); //输出DFA

cout<<\"其中终态为：\"<精选

}

5.. 实验截图：

精选