實驗名稱正規表示式與有限自動機
院系資訊工程學院
班級電腦科學與技術1班
學號2013550336
姓名朱義
1、實驗目的
通過本次實驗，加深對正規表示式，nfa，dfa及其識別的語言的理解
二、實驗題目
程式設計實現nfa確定化為nfa的過程
3、演算法思想
1. 乙個自動機是乙個五元組，分別是《狀態集，符號集，f函式，起始狀態，終止狀態》
2. 使用子集法的步驟是：
1) 將起始狀態求閉包，得到s0。
2) 從0開始直到totss對每個子集求各個字元所能到達的新子集將其加入tot+1子集中。
3) 檢查tot+1子集是否與之前的子集重合或者為空,如果重合或為空則子集不增加。
4) 記錄新的狀態轉換函式。
3. 根據nfa轉化為dfa的過程一步步模擬進行操作。
4、資料結構介紹
程式裡將nfa五元組分別儲存在以下資料結構裡
初態集儲存在 int陣列 sta_statu[maxs]裡 maxs為元素的最大數
終態集儲存在 int陣列 end_statu[maxs]裡
字符集儲存在 char陣列 cha[maxs]裡
狀態儲存為0~n-1（n個狀態情況）
狀態轉換函式儲存於結構 stuct statu裡
struct edge;
struct statu
}}sta[50];//起點
5、具體實現
使用子集法實現：
函式介面解釋：
void creat_subset(void); 構造子集函式
ins(int a,int ss) 用深搜（dfs）求狀態ss的閉包，並將閉包裡的所有元素加入到子集closure[a]裡。
void ins_subset(int a,int ss,char target) 求狀態ss通過字元target所能到達的所有狀態，並將這些狀態加入到子集closure[a]裡。
int check(int tt) 檢查子集closure[tt]是否與之前的子集重合，為空則返回-2，不重合返回-1，重合則返回重合的子集下標。
void print(void) 輸出dfa的五元組資訊。
1.將起始狀態求閉包，得到s0。
將初狀態裡所有的元素及其能通過e空路所到的狀態加入closure[0]作為初始子集
for(int i=0;i
closure[0].members.insert(sta_statu[i]);
ins(0,sta_statu[i]);
e_closure(s0)
2.從0開始直到totss對每個子集求各個字元所能到達的新子集將其加入tot+1子集中。
for(tempss=0;tempss<=totss;tempss++)//tempss 表示當前運算的狀態下表 totss表示總共的狀態數新生產的狀態子集加入到 closur[tot+1]中
for(int j=0;jfor(it=closure[tempss].members.begin();it!
=closure[tempss].members.end();it++)
ins_subset(totss+1,*it,cha[j]);
}void ins_subset(int a,int beg,char target)// 求狀態ss通過字元target所能到達的所有狀態，並將這些狀態加入到子集closure[a]裡。
} return ;}
void ins(int a,int beg)//求集合的ε 閉包
}}3.檢查tot+1子集是否與之前的子集重合或者為空,如果重合或為空則子集不增加
int check(int tt)
if(isb==closure[tt].members.end())
return i; //重合則返回之前相同的子集的下標
}return -1;//不重合返回-1
}4.記錄新的狀態轉換函式
if(ok==-2)//新子集為空
;else if(ok==-1) //與之前的子集不重合，記錄新狀態轉換函式
totss++;
newsta[tempss].node[newsta[tempss].cnt].cost=cha[j];
newsta[tempss].node[newsta[tempss].cnt++].dest=totss;
else//與之前的子集重合，記錄新狀態轉換函式
closure[totss+1].members.clear();
newsta[tempss].node[newsta[tempss].cnt].cost=cha[j];
newsta[tempss].node[newsta[tempss].cnt++].dest=ok;
5.輸出dfa資訊
六、設計過程中的問題與對策
nfa轉化為dfa的過程中最難解決的是如何儲存狀態轉換函式以及記錄新的狀態轉換函式的問題，我開始設計為乙個二維陣列，實際應用時發現當nfa中乙個字元對應兩個目標時前乙個目標會被覆蓋。於是再仔細觀察nfa的特點，多個初態，多個終態，乙個狀態經乙個字元可對應多個狀態。設計了一種新的儲存結構，因為每個nfa相當於乙個有向圖。
用乙個結構體儲存每個狀態的邊數，每個邊的消耗及重點。然後即可順利進行了。
7、測試與運**況
樣例1輸出
樣例2輸出
樣例3輸出
8、實驗總結
這次實驗讓我加深了對nfa,dfa的理解，實現編寫nfa到dfa的轉化過程中遇到了許多困難，讓我不斷地去查閱資料，增長了自己的知識，豐富了自己的實踐經驗。
編譯實驗三 NFA轉換成DFA和DFA化簡 要點
實驗三 一 nfadfa 2小時 一.問題描述 nfadfa。1.實驗目的 學會程式設計實現子集構造法。2.實驗任務 儲存nfa與dfa，程式設計實現子集構造法將nfa轉換成dfa。3.實驗內容 1 確定nfa與dfa的儲存格式，為3個以上測試nfa準備好儲存檔案。2 用c或j a語言編寫將nfa轉...
編譯原理實驗
實驗三中間的 優化 一 實驗目的 掌握區域性優化方法 提高機器的執行速度 二 相關知識 某些編譯程式在中間 或目標 生產之後要對其進行優化，所謂優化就是對 進行等價的變換。而變換後的 執行結果與變換前的 執行結果相同。而執行速度加快或占用記憶體空間減少。中間的 優化就是對中間 進行等價的變換。基本塊...
編譯原理實驗
第一篇高階程式語言到中間語言 第一章編譯概論及程式語言規定 1 1 編譯程式概論 計算機執行乙個高階語言程式一般要分為兩步 第一步，用乙個編譯程式把高階語言翻譯成機器語言程式 第二步，執行所得的機器語言程式，求得計算結果。編譯程式的工作貫穿於從輸入源程式開始到輸出目標程式為止的整個過程，是非常複雜的...