背景

期末考試免考，沖！

實驗名稱

對任意給定的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到DFA的轉換及DFA的簡化

實驗過程

對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<cnt;i++)change[ans[i]]=i+'A'; //輸出處理，用字母'A'-'Z'來表示集合

對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<st->setJ.length();i++){for(int j=0;j<cntEdge;j++){ //遍歷所有的邊if(st->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得到dfor(int i=0;i<source->setJ.length();i++){for(int j=0;j<cntEdge;j++){ //遍歷所有的邊if(source->setJ[i] == e[j].preNode && e[j].tchar == ttchar)dest->setJ+=e[j].nexNode;}} }

去重操作，判斷是否加入 allSet（總狀態集合） 中

//通過狀態集合中的setJ來決定是否添加 bool isInsert(vector<newJ*> allSet,newJ* newSet){for(int i=0;i<allSet.size();i++){if(allSet.at(i)->setJ == newSet->setJ)return false;}return true; }

去重操作，判斷當前狀態轉換是否加入轉換關系表中

//判斷relation結構體去重 bool isInsertForRel(vector<relation*> relVec,newJ* preJ,char jchar,newJ* nexJ){for(int i=0;i<relVec.size();i++){if(relVec.at(i)->preJ->setJ == preJ->setJ && relVec.at(i)->jchar == jchar && relVec.at(i)->nexJ->setJ == nexJ->setJ)return false;}return true; }

重命名轉換函數

//重命名轉換函數 void changeName(vector<newJ*> allSet,newJ* newSet,string& newStr){newJ* tmpJ = new newJ();for(int i=0;i<allSet.size();i++){if(allSet.at(i)->setJ == newSet->setJ)tmpJ->setJ = 'A'+i;}newStr = tmpJ->setJ; }

后續省略…（詳情請見后文源代碼說明）

實驗結果（附源代碼）

對 NFA M 確定化

#include<bits/stdc++.h> #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<<"多組輸入，請先輸入對應的組數:"<<endl;cin>>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<<"輸入終止狀態集合，結束以'$'開頭"<<endl;char endNode;while(cin>>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<cnt;i++)if(ans[i]&f) //判斷所求集合中是否包含終態ac[i]=1,sum++; //標記終態集合并統計個數for(int i=0;i<cnt;i++)change[ans[i]]=i+'A'; //輸出處理，用字母'A'-'Z'來表示集合cout<<"轉換結果:"<<endl;cout<<"DFA的狀態數:"<<cnt<<" "<<"終止狀態數:"<<sum<<endl<<endl;cout<<"終態:"<<endl; //輸出終態集合for(int i=0,j=0;i<cnt;i++){if(ac[i]){if(j)cout<<" ";cout<<(char)(i+'A');j++;}}cout<<endl<<endl; //輸出DFA狀態轉換矩陣cout<<"由NFA得到的DFA狀態轉換矩陣:"<<endl;cout<<"----------------------------"<<endl;cout<<" "<<"a"<<" "<<"b"<<endl;cout<<"----------------------------"<<endl;for(int i=0;i<cnt;i++) //輸出打印新的轉換結果cout<<(char)('A'+i)<<" "<<change[lft[i]]<<" "<<change[rgt[i]]<<endl;cout<<"----------------------------"<<endl;cout<<endl;}return 0; }

輸出結果

輸出結果文字版

多組輸入，請先輸入對應的組數: 100 輸入各邊的信息,并且以 '前點(char '0'-'1000') 轉換字符(a 或 b) 后點(int '0'-'1000')'格式，結束以'$'開頭 0 b 2 4 a 0 0 a 1 1 a 1 2 b 3 3 b 2 3 a 3 5 a 5 4 b 5 5 b 4 1 b 4 2 a 1 $ 輸入終止狀態集合，結束以'$'開頭 0 $ 轉換結果: DFA的狀態數:6 終止狀態數:1終態: A由NFA得到的DFA狀態轉換矩陣: ----------------------------a b ---------------------------- A B E B B C C A D D D C E B F F F E ----------------------------

對NFA N 確定化

#include<bits/stdc++.h> 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<st->setJ.length();i++){for(int j=0;j<cntEdge;j++){ //遍歷所有的邊if(st->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得到dfor(int i=0;i<source->setJ.length();i++){for(int j=0;j<cntEdge;j++){ //遍歷所有的邊if(source->setJ[i] == e[j].preNode && e[j].tchar == ttchar)dest->setJ+=e[j].nexNode;}} } //通過狀態集合中的setJ來決定是否添加 bool isInsert(vector<newJ*> allSet,newJ* newSet){for(int i=0;i<allSet.size();i++){if(allSet.at(i)->setJ == newSet->setJ)return false;}return true; } //判斷relation結構體去重 bool isInsertForRel(vector<relation*> relVec,newJ* preJ,char jchar,newJ* nexJ){for(int i=0;i<relVec.size();i++){if(relVec.at(i)->preJ->setJ == preJ->setJ && relVec.at(i)->jchar == jchar && relVec.at(i)->nexJ->setJ == nexJ->setJ)return false;}return true; } //重命名轉換函數 void changeName(vector<newJ*> allSet,newJ* newSet,string& newStr){newJ* tmpJ = new newJ();for(int i=0;i<allSet.size();i++){if(allSet.at(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<maxn;i++){cin>>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<cntEdge;i++){char preTmp = e[i].preNode;char nexTmp = e[i].nexNode;if(node.find(preTmp)>node.length()) node+=preTmp;if(node.find(nexTmp)>node.length()) node+=nexTmp;}cout<<"輸入初始點字符:"<<endl;cin>>staNode;while(node.find(staNode)==string::npos){cout<<"初始狀態輸入錯誤，請重新輸入:"<<endl;cin>>staNode; //錯誤即重新輸入一次}cout<<"輸入終止點字符(若有多個終結狀態，直接寫成字符串形式)"<<endl;cin>>endNode;bool inputStatus=true; //用于結束終止點字符的輸入while(inputStatus){for(int i=0;i<endNode.length();i++){if(node.find(endNode[i])==string::npos){cout << "終結狀態輸入錯誤，請重新輸入:" << endl;cin >> endNode;}}inputStatus=false;}newJ* newSet = new newJ();newSet->setJ = staNode; //設置初始點為狀態集合IgetEClosure(e, cntEdge, newSet); //得到閉包vector<newJ*>allSet(1, newSet); //設置所有狀態集合的向量/*用來存儲每一次的閉包操作前的第一列的狀態集合*比如第一次strVec存儲的是初始狀態，求閉包時多了2個狀態集合。在第二次時存儲的是新的2個狀態，原先的初始狀態被去除。*總的狀態集合存儲在allSet中*/vector<newJ*>strVec(1, newSet);int sizeOfStrVec = 1; //初始大小就是初始點所構成的狀態集合vector<relation*>relVec; //轉換關系表的向量while(sizeOfStrVec){ //如果不符合則說明新增的集合都是原有的集合int oldAllSize=allSet.size(); //求出目前存儲的狀態集合大小for(int j=0;j<sizeOfStrVec;j++){for(int i=0;i<cntEdge;i++){newJ* dest=new newJ();if(!cntRealEdge[i]){ //不是空字符邊的，對它進行move操作moveT(e[i].tchar, e, cntEdge, strVec.at(j), dest);//如果有一個字符在多條邊上，所以要按字符相同的歸類集合。否則就會使得狀態集合分開而造成錯誤！！getEClosure(e, cntEdge, dest); //此時dest為 Ia,Ib之類的if(isInsert(allSet,dest) && dest->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<allSet.size();i++){//將allSet中新增的后面元素添加進strVec中newJ* dest = new newJ();dest = allSet.at(i);strVec.push_back(dest);}sizeOfStrVec = strVec.size(); //求出目前存儲的狀態集合大小}cout << "轉換結果:" << endl;vector<relation*>::iterator relIt;for(relIt=relVec.begin();relIt!=relVec.end();relIt++) //遍歷輸出關系轉換表的集合cout<<(*relIt)->preJ->setJ<<" "<<(*relIt)->jchar<<" "<<(*relIt)->nexJ->setJ<<endl;char upperChars[26];memset(upperChars,0,sizeof(upperChars));cout<<"重命名如下:"<<endl;for(int i=0;i<allSet.size();i++){upperChars[i] = 'A'+i; //通過下標將每一個集合依次從'A'開始 命名cout<<upperChars[i]<<":"<<allSet.at(i)->setJ<<endl;}vector<relation*> newRelVec; //重命名后的relVec;for(int i=0;i<relVec.size();i++){relation* newRel = new relation(); //依次更換新的名稱string preNew,nexNew;changeName(allSet,relVec.at(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<relation*>::iterator newRelIt;for(newRelIt = newRelVec.begin();newRelIt!=newRelVec.end();newRelIt++) //遍歷輸出新的關系轉換表的集合cout<<(*newRelIt)->preJ->setJ<<" "<<(*newRelIt)->jchar<<" "<<(*newRelIt)->nexJ->setJ<<endl;//輸出終止狀態cout<<"終態:"<<endl;set<char> st; //通過set來進行去重操作set<char>::iterator it;for(int k=0;k<allSet.size();k++){for(int i=0;i<endNode.size();i++){if(allSet.at(k)->setJ.find(endNode[i]) != string::npos) //確保終態在集合中存在st.insert('A'+k); //放入set集合中，達到去重效果}}for(it=st.begin();it!=st.end();it++) cout<<(*it)<<" "; //遍歷輸出終態集合cout<<endl;return 0; }

輸出結果

輸出結果文字版

輸入各邊的信息,并且以 '前點(char '0'-'1000') 轉換字符(char 'a'-'z') 后點(char '0'-'1000')'格式，結束以'$'開頭 如果轉換字符為空，則用'#'表示 a 1 b b 1 b b 2 b b # e a # c c 1 c c 2 c c 1 d $ 輸入初始點字符: a 輸入終止點字符(若有多個終結狀態，直接寫成字符串形式) ed 轉換結果: ac 1 bcde ac 2 c bcde 1 bcde bcde 2 bce c 1 cd c 2 c bce 1 bcde bce 2 bce cd 1 cd cd 2 c 重命名如下: A:ac B:bcde C:c D:bce E:cd 最終轉換： A 1 B A 2 C B 1 B B 2 D C 1 E C 2 C D 1 B D 2 D E 1 E E 2 C 終態: B D E

參考文獻

感謝以下博主的文章，本文參考了部分代碼和知識。

Hungryof：NFA到DFA的轉換

zhen12321：編譯原理-(NFA->DFA)

發芽ing的小啊嗚：【20200319】編譯原理課程課業打卡九之NFA的確定化

Just-Live：湖大OJ-實驗C----NFA轉換為DFA

愛玩游戲的小隱：正則到NFA的轉換

愛玩游戲的小隱：NFA到DFA的轉換及DFA的簡化

學如逆水行舟，不進則退

總結

以上是生活随笔為你收集整理的【C++实现】编译原理 免考小队 NFA转换为等价的DFA的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。