本文共 11255 字，大约阅读时间需要 37 分钟。

背景

期末考试免考，冲！

实验名称

对任意给定的NFA M进行确定化操作

实验时间

2020年5月21日 到 2020年5月24日

院系

信息科学与工程学院

组员姓名

Chocolate、kry2025、钟先生、leo、小光

实验环境介绍

• windows 10 操作系统
• Eclipse 进行 java 编程
• CodeBlocks 进行 C++ 编程

实验目的与要求

目的

• 深刻理解 NFA 确定化操作
• 掌握子集构造算法过程
• 加强团队合作能力
• 提高自身的编程能力和解决问题的能力

要求

NFA 转换为等价的 DFA

正则 到 NFA的转换

有穷自动机

作用：将输入的序列转换成一个状态图，方便之后的处理。通常被用在词法分析器中。

1）有穷自动机是一个识别器，对每个可能的的输入串简单的回答“是”或“否”。 2）有穷自动机分为两类： a)不确定的有穷自动机（NFA）对其边上的标号没有任何限制。一个符号标记离开同一状态的多条变，并且空串ε也可以作为标号。 b)确定的有穷自动机（DFA）有且只有一条离开该状态，以该符号位标号的边。

不确定的有穷自动机

正则式（RE）转不确定型有穷自动机（NFA）

找出所有可以被匹配的字符即符号集合∑作为每一列的字段名，然后从起始态开始 1）状态0可以匹配a，匹配后可以到状态0或状态1，记为∅。匹配b只能得到状态0，记为{0}。 2）状态1可以匹配a，没有匹配到，记为∅。匹配b得到状态2，记为{2}。 3）状态0可以匹配a，没有匹配到，记为∅。匹配b得到状态3，记为{3}。 4）状态0可以匹配a，没有匹配到，记为∅。匹配b没有匹配到，记为∅。

至此，状态表建立完成。正则式（RE）转不确定型有穷自动机（NFA）完成。

NFA 到 DFA

NFA M 确定化

1）根据NFA构造DFA状态转换矩阵：

• ①确定DFA的字母表，初态（NFA的所有初态集）
• ②从初态出发，经字母表到达的状态集看成一个新状态
• ③将新状态添加到DFA状态集
• ④重复②③步骤，直到没有新的DFA状态

2）画出DFA

3）看NFA和DFA识别的符号串是否一致

NFA N 确定化

涉及操作：

算法：

实验过程

对NFA M 确定化

采用二进制方法来对NFA M 进行确定化，先来说说其中用到的关键知识：

将状态集合用二进制表示，例如，如果一个集合（从0开始）包含了 0,1,2，总共有4个状态（即 0,1,2,3 ），那么，当前集合用 0111 表示。同理，如果包含了0,3 ，总共有4个状态（即 0,1,2,3 ），那么，当前集合用 1001 表示。

x & (-x) 表示拿到 x 的最右边第一个

a & x 可以判断 a 状态集合 是否包含 x 状态集合

a ^= x 可以用来将 x 状态集合 加入到 a 状态集合

下面依次来讲述代码实现：

int ans[maxn],one[maxn],zero[maxn],lft[maxn],rgt[maxn];char change[maxn];bool vis[maxn],ac[maxn];

用到的数据结构：

• ans 数组表示所求的状态集合
• one 数组表示状态经 1 所到达的状态
• zero 数组表示状态经 0 所到达的状态
• lft 数组表示经过 0 状态到达的状态集合
• rgt 数组表示经过 1 状态到达的状态集合
• change 数组用来转换输出结果，即将状态集合用字母 ‘A’-‘Z’ 来表示
• vis 数组用来去重操作，判断当前状态集合是否存在过
• ac 数组用来判断集合状态中是否包含终态，若包含，置为1

下面函数是用来找到对应状态下标

//找到对应的状态下标int index(int p){
       int x = 1;    if(p == 1)  //p为1表示当前为初始状态        return 0;    int i = 0;    while(++i){
     //循环找出当前对应的状态下标        x <<= 1;        if(p == x)            return i; //找到即返回对应下标    }    return 0;}

move操作

int moveT(int a, int b){
       while(b){
           int x = b&(-b);  //去当前集合中的最后一个节点        if(!(a&x))   //如果不存在该节点，加入集合当中            a ^= x;        b ^= x;  //已经存在该节点，就进行舍去操作    }    return a;}

核心代码，将状态集合逐个拿出来，进行 move 操作，然后进行去重操作，最后进行更新新的状态集合

void dfs(int p){
       ans[cnt] = p;    int lsum = 0, rsum = 0;    while(p){
           int x = p&(-p);  //取出当前集合中的最后一个节点        int y = index(x); //找到对应的状态下标        lsum = moveT(lsum, zero[y]); //进行move操作        rsum = moveT(rsum, one[y]);  //进行move操作        p ^= x;   //将当前拿出来的节点从原集合中去掉    }    lft[cnt] = lsum;  //更新当前的状态集合    rgt[cnt] = rsum;  //更新当前的状态集合    cnt++;            //更新状态行数    if(!vis[lsum])        vis[lsum] = 1, dfs(lsum);  //进行去重操作    if(!vis[rsum])        vis[rsum] = 1, dfs(rsum); //进行去重操作}

输入处理

while(cin>>preNode){
       if(preNode=='$') break;    cin>>tchar>>nexNode;    if(tchar-'a'==0) zero[preNode-'0']|=(1<<(nexNode-'0'));    else one[preNode-'0']|=(1<<(nexNode-'0'));}

输出处理

for(int i=0;i

对NFA N 确定化

用到的数据结构：

struct edge{
       char preNode;  //前驱节点    char tchar;    //弧    char nexNode;  //后继节点}e[maxn];//获得的状态集合struct newJ{
       string setJ;};//集合与集合之间的转换关系struct relation{
       newJ* preJ;    char jchar;    newJ* nexJ;};

• edge 结构体用来表示边的信息
• newJ 表示状态集合J
• relation 结构体表示最后输出的转换关系表

求某个状态的闭包

//得到闭包void getEClosure(const edge* e,int cntEdge,newJ* st){
       for(int i=0;i
   
    setJ.length();i++){
           for(int j=0;j
    
     setJ[i] == e[j].preNode && e[j].tchar=='#')                st->setJ+=e[j].nexNode;        }    }}
    
   

move操作

//move操作void moveT(char ttchar,const edge* e,int cntEdge,newJ* source,newJ* dest){
       //e为所有边的集合，然后就能从一个转换字符得到全部的，比如2得到bd，而不会第一个2得到b，第二个2得到d    for(int i=0;i
   
    setJ.length();i++){
           for(int j=0;j
    
     setJ[i] == e[j].preNode && e[j].tchar == ttchar)                dest->setJ+=e[j].nexNode;        }    }}
    
   

去重操作，判断是否加入 allSet（总状态集合） 中

//通过状态集合中的setJ来决定是否添加bool isInsert(vector
   
     allSet,newJ* newSet){
       for(int i=0;i
    
     setJ == newSet->setJ)            return false;    }    return true;}
    
   

去重操作，判断当前状态转换是否加入转换关系表中

//判断relation结构体去重bool isInsertForRel(vector
   
     relVec,newJ* preJ,char jchar,newJ* nexJ){
       for(int i=0;i
    
     preJ->setJ == preJ->setJ && relVec.at(i)->jchar == jchar && relVec.at(i)->nexJ->setJ == nexJ->setJ)            return false;    }    return true;}
    
   

重命名转换函数

//重命名转换函数void changeName(vector
   
     allSet,newJ* newSet,string& newStr){
       newJ* tmpJ = new newJ();    for(int i=0;i
    
     setJ == newSet->setJ)            tmpJ->setJ = 'A'+i;    }    newStr = tmpJ->setJ;}
    
   

后续省略…（详情请见后文源代码说明）

实验结果（附源代码）

对 NFA M 确定化

#include
   
    #define endl '\n'using namespace std;const int maxn=999999;int ans[maxn],one[maxn],zero[maxn],lft[maxn],rgt[maxn];char change[maxn];bool vis[maxn],ac[maxn];int cnt,n,q,f;//找到对应的状态下标int index(int p){
       int x = 1;    if(p == 1)  //p为1表示当前为初始状态        return 0;    int i = 0;    while(++i){
     //循环找出当前对应的状态下标        x <<= 1;        if(p == x)            return i; //找到即返回对应下标    }    return 0;}int moveT(int a, int b){
       while(b){
           int x = b&(-b);  //去当前集合中的最后一个节点        if(!(a&x))   //如果不存在该节点，加入集合当中            a ^= x;        b ^= x;  //已经存在该节点，就进行舍去操作    }    return a;}void dfs(int p){
       ans[cnt] = p;    int lsum = 0, rsum = 0;    while(p){
           int x = p&(-p);  //取出当前集合中的最后一个节点        int y = index(x); //找到对应的状态下标        lsum = moveT(lsum, zero[y]); //进行move操作        rsum = moveT(rsum, one[y]);  //进行move操作        p ^= x;   //将当前拿出来的节点从原集合中去掉    }    lft[cnt] = lsum;  //更新当前的状态集合    rgt[cnt] = rsum;  //更新当前的状态集合    cnt++;            //更新状态行数    if(!vis[lsum])        vis[lsum] = 1, dfs(lsum);  //进行重复操作    if(!vis[rsum])        vis[rsum] = 1, dfs(rsum); //进行重复操作}int main(){
       int t;    cout<<"多组输入，请先输入对应的组数:"<
    
     >t;  //多组输入    while(t--){
           cout << "输入各边的信息,并且以 '前点(char '0'-'1000')   转换字符(a 或 b)   后点(int '0'-'1000')'格式，结束以'$'开头" << endl;        char preNode,tchar,nexNode;        while(cin>>preNode){
               if(preNode=='$') break;            cin>>tchar>>nexNode;            if(tchar-'a'==0) zero[preNode-'0']|=(1<<(nexNode-'0'));            else one[preNode-'0']|=(1<<(nexNode-'0'));        }        q=1;        cout<<"输入终止状态集合，结束以'$'开头"<
     
      >endNode){
               if(endNode=='$') break;            f|=(1<<(endNode-'0'));        }        cnt=0;        memset(vis,0,sizeof(vis)); //初始化        memset(ac,0,sizeof(ac)); //初始化        vis[q]=1;        dfs(q);    //转换开始        int sum=0;        for(int i=0;i
     
    
   

输出结果

输出结果文字版

多组输入，请先输入对应的组数:100输入各边的信息,并且以 '前点(char '0'-'1000')   转换字符(a 或 b)   后点(int '0'-'1000')'格式，结束以'$'开头0 b 24 a 00 a 11 a 12 b 33 b 23 a 35 a 54 b 55 b 41 b 42 a 1$输入终止状态集合，结束以'$'开头0$转换结果:DFA的状态数:6 终止状态数:1终态:A由NFA得到的DFA状态转换矩阵:----------------------------  a b----------------------------A B EB B CC A DD D CE B FF F E----------------------------

对NFA N 确定化

#include
   
    using namespace std;const int maxn=1000;struct edge{
       char preNode;  //前驱节点    char tchar;    //弧    char nexNode;  //后继节点}e[maxn];//获得的状态集合struct newJ{
       string setJ;};//集合与集合之间的转换关系struct relation{
       newJ* preJ;    char jchar;    newJ* nexJ;};//得到闭包void getEClosure(const edge* e,int cntEdge,newJ* st){
       for(int i=0;i
    
     setJ.length();i++){
           for(int j=0;j
     
      setJ[i] == e[j].preNode && e[j].tchar=='#')                st->setJ+=e[j].nexNode;        }    }}//move操作void moveT(char ttchar,const edge* e,int cntEdge,newJ* source,newJ* dest){
       //e为所有边的集合，然后就能从一个转换字符得到全部的，比如2得到bd，而不会第一个2得到b，第二个2得到d    for(int i=0;i
      
       setJ.length();i++){
           for(int j=0;j
       
        setJ[i] == e[j].preNode && e[j].tchar == ttchar)                dest->setJ+=e[j].nexNode;        }    }}//通过状态集合中的setJ来决定是否添加bool isInsert(vector
        
          allSet,newJ* newSet){ for(int i=0;i
         
          setJ == newSet->setJ) return false; } return true;}//判断relation结构体去重bool isInsertForRel(vector
          
            relVec,newJ* preJ,char jchar,newJ* nexJ){ for(int i=0;i
           
            preJ->setJ == preJ->setJ && relVec.at(i)->jchar == jchar && relVec.at(i)->nexJ->setJ == nexJ->setJ) return false; } return true;}//重命名转换函数void changeName(vector
            
              allSet,newJ* newSet,string& newStr){ newJ* tmpJ = new newJ(); for(int i=0;i
             
              setJ == newSet->setJ) tmpJ->setJ = 'A'+i; } newStr = tmpJ->setJ;}int main(){ int cntEdge=0; //统计边的数量 char staNode; //初始状态点 string endNode,node; //终止状态节点和总的节点集合 int cntRealEdge[maxn]={ 0}; //用于判断是否包含空字符的边 为1代表含空字符的边 初始话为0，不包含 cout << "输入各边的信息,并且以 '前点(char '0'-'1000') 转换字符(char 'a'-'z') 后点(char '0'-'1000')'格式，结束以'$'开头" << endl; cout << "如果转换字符为空，则用'#'表示" << endl; char ttchar[2]; for(int i=0;i
              
               >e[i].preNode; //输入前点 if(e[i].preNode == '$') break; //遇到'$' 结束输入 cin>>ttchar; cin>>e[i].nexNode; //输入转换字符及后点 e[i].tchar=ttchar[0]; if(ttchar[0] == '#') cntRealEdge[cntEdge]=1; //标记含有空字符的边 ++cntEdge; //统计边的数量 } //将输入的边节点进行整合 for(int i=0;i
               
                node.length()) node+=preTmp; if(node.find(nexTmp)>node.length()) node+=nexTmp; } cout<<"输入初始点字符:"<
                
                 >staNode; while(node.find(staNode)==string::npos){ cout<<"初始状态输入错误，请重新输入:"<
                 
                  >staNode; //错误即重新输入一次 } cout<<"输入终止点字符(若有多个终结状态，直接写成字符串形式)"<
                  
                   >endNode; bool inputStatus=true; //用于结束终止点字符的输入 while(inputStatus){ for(int i=0;i
                   
                    > endNode; } } inputStatus=false; } newJ* newSet = new newJ(); newSet->setJ = staNode; //设置初始点为状态集合I getEClosure(e, cntEdge, newSet); //得到闭包 vector
                    
                     allSet(1, newSet); //设置所有状态集合的向量 /*用来存储每一次的闭包操作前的第一列的状态集合 *比如第一次strVec存储的是初始状态，求闭包时多了2个状态集合。在第二次时存储的是新的2个状态，原先的初始状态被去除。 *总的状态集合存储在allSet中 */ vector
                     
                      strVec(1, newSet); int sizeOfStrVec = 1; //初始大小就是初始点所构成的状态集合 vector
                      
                       relVec; //转换关系表的向量 while(sizeOfStrVec){ //如果不符合则说明新增的集合都是原有的集合 int oldAllSize=allSet.size(); //求出目前存储的状态集合大小 for(int j=0;j
                       
                        setJ!="") //没找到并且dest->setJ且不为空则添加 allSet.push_back(dest); //在添加relVec时，只要是不为空就要添加，这里会使relDest的元素可能重复（当一个字符出现在多条边中） if (dest->setJ != ""){ relation* relDest = new relation(); relDest->preJ = strVec.at(j); relDest->jchar = e[i].tchar; relDest->nexJ = dest; bool isIN = isInsertForRel(relVec,relDest->preJ,relDest->jchar,relDest->nexJ); //去重 if(isIN) relVec.push_back(relDest); } } } } strVec.clear(); //去除原状态集合 for(int i=oldAllSize;i
                        
                         ::iterator relIt; for(relIt=relVec.begin();relIt!=relVec.end();relIt++) //遍历输出关系转换表的集合 cout<<(*relIt)->preJ->setJ<<" "<<(*relIt)->jchar<<" "<<(*relIt)->nexJ->setJ<
                         
                          setJ<
                          
                            newRelVec; //重命名后的relVec; for(int i=0;i
                           
                            preJ,preNew); changeName(allSet,relVec.at(i)->nexJ,nexNew); newJ* tpreJ = new newJ(); newJ* tnexJ = new newJ(); newRel->preJ = tpreJ; newRel->nexJ = tnexJ; newRel->preJ->setJ = preNew; newRel->nexJ->setJ = nexNew; newRel->jchar = relVec.at(i)->jchar; newRelVec.push_back(newRel); } //输出验证重命名的集合关系 cout << "最终转换：" << endl; vector
                            
                             ::iterator newRelIt; for(newRelIt = newRelVec.begin();newRelIt!=newRelVec.end();newRelIt++) //遍历输出新的关系转换表的集合 cout<<(*newRelIt)->preJ->setJ<<" "<<(*newRelIt)->jchar<<" "<<(*newRelIt)->nexJ->setJ<
                             
                               st; //通过set来进行去重操作 set
                              
                               ::iterator it; for(int k=0;k
                               
                                setJ.find(endNode[i]) != string::npos) //确保终态在集合中存在 st.insert('A'+k); //放入set集合中，达到去重效果 } } for(it=st.begin();it!=st.end();it++) cout<<(*it)<<" "; //遍历输出终态集合 cout<
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

输出结果

输出结果文字版

输入各边的信息,并且以 '前点(char '0'-'1000')   转换字符(char 'a'-'z')   后点(char '0'-'1000')'格式，结束以'$'开头如果转换字符为空，则用'#'表示a 1 bb 1 bb 2 bb # ea # cc 1 cc 2 cc 1 d$输入初始点字符:a输入终止点字符(若有多个终结状态，直接写成字符串形式)ed转换结果:ac 1 bcdeac 2 cbcde 1 bcdebcde 2 bcec 1 cdc 2 cbce 1 bcdebce 2 bcecd 1 cdcd 2 c重命名如下:A:acB:bcdeC:cD:bceE:cd最终转换：A 1 BA 2 CB 1 BB 2 DC 1 EC 2 CD 1 BD 2 DE 1 EE 2 C终态:B D E

参考文献

感谢以下博主的文章，本文参考了部分代码和知识。

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/106282528 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！