實驗三（一）nfadfa（2小時）
一. 問題描述
nfadfa。
1. 實驗目的：學會程式設計實現子集構造法。
2. 實驗任務：儲存nfa與dfa，程式設計實現子集構造法將nfa轉換成dfa。
3. 實驗內容：（1）確定nfa與dfa的儲存格式，為3個以上測試nfa準備好儲存檔案。
（2）用c或j**a語言編寫將nfa轉換成dfa的子集構造法的程式。（3）經測試無誤。測試不易。
可求出nfa與dfa的語言集合的某個子集（如長度小於某個n），再證實兩個語言集合完全相同！（4）測試用例參考：將下列語言用re表示，再轉換成nfa使用：
(a) 以a開頭和結尾的小字字母串；a (a|b|…|z)*a | a
(b) 不包含三個連續的b的，由字母a與b組成的字串；( | b | bb) (a | ab | abb)*
(c) (aa|b)*(a|bb)*
二．演算法描述
1. nfa的輸入：
分別輸入nfa的「字符集」、「狀態集」、「開始狀態」、「接受狀態集」、「狀態轉換表」等內容，並儲存在設定的變數中。
2. nfa的儲存與讀寫：
將上述nfa的五元組儲存在乙個文字檔案中。儲存格式如下所示（以下圖中nfa為例）：
2 // 字符集中的字元個數 (以下兩行也可合併成一行)
a b // 以空格分隔的字符集。
4 // 狀態個數 (以下兩行也可合併成一行)
1 2 3 4 // 狀態編號。若約定總是用從1開始的連續數字表示，則此行可省略
1 // 開始狀態的編號。若約定為1，則此行可省略
1 // 結束狀態個數。若約定為1，則此行可省略
3 // 結束狀態的編號
3 2 1 // 狀態1的所有出去的轉換。按字符集中的字元順序給出，並在最左邊加上一列關於的轉換。-1表示出錯狀態。多個狀態用逗號分隔。
-1 1 -1
-1 3 4
-1 -1 3
3. 基本演算法描述
儲存格式如上所示，程式開始時，從檔案中讀取資料以獲得nfa中的各種資訊。根據子集構造法，構造相應的函式。
子集構造法偽**如下：
初始時,ε-closure(s0)是dstates中唯一的狀態且未被標記;
whiledstates中存在乙個未標記的狀態tdobegin
標記t;
for每個輸入符號adobegin
u:=ε-closure(move(t,a));
ifu沒在dstates中then
將u作為乙個未被標記的狀態新增到dstates.
dtran[t,a]:=u
endend
ε-closure的計算
將t中所有狀態壓入棧stack;
將ε-closure(t)初始化為t;
whilestack不空dobegin
將棧頂元素t彈出棧;
for每個這樣的狀態u：從t到u有一條標記為ε的邊do
ifu不在ε-closure(t)中dobegin
將u新增到ε-closure(t);
將u壓入棧stack中
endend
子集構造法的流程圖：
實驗三（二）dfa化簡（2小時）
一. 問題描述
dfa化簡
1．實驗目的：學會程式設計實現等價劃分法化簡dfa。
2．實驗任務：先完善dfa，再化簡dfa。
3．實驗內容：
（1）準備3個以上測試dfa檔案。
（2）dfa手動完善。（狀態轉換對映要是滿對映）
（3）用c或j**a語言編寫用等價劃分法化簡dfa的程式。
（4）經測試無誤。測試不易。可求出兩個dfa的語言集合的某個子集（如長度小於某個n），再證實兩個語言集合完全相同！
（5）編寫實驗報告。要求同實驗一，不再詳述。
二．演算法描述
的化簡得到新的dfa之後，並沒有完成任務，因為通過nfa轉化成dfa不一定是最簡的，也就是說，有多餘的狀態可以被刪除，而我們需要的是得到乙個唯一的最簡的dfa[12]，也就是說，nfa轉化為dfa之後，還需要化簡，也就是最小化。
2.化簡的理論基礎
dfa的化簡是指：尋找乙個狀態數最少的dfam，使得l（m）=l（m』）。化簡的方法是消去dfam中的多餘狀態（或無用狀態），合併等價狀態。
dfa中的多餘狀態是指這樣的狀態：從開始狀態出發，讀入任何輸入串都不能到達的那個狀態；或者從這個狀態沒有通路到達終態。
兩個狀態s和t等價是指：如果從狀態s出發能讀出某個字w而停於終態，從t出發也能讀出同樣的字w而停於終態；反之，從t出發能讀出同樣的字w而停於終態，從s出發也能讀出某個字w而停於終態。
3.化簡的基本思想
化簡dfa的基本思想是指導它的狀態分成一些互不相交的子集，每乙個子集中的狀態都不是等價的，不同子集中的狀態可以由某個輸入串來區別，最後將不能區別的每個子集用乙個狀態來做代表[13-15]，這種方法稱為「分割法」。具體過程是：
（1）將m的所有狀態分成兩個子集——終態集和非終態集；
（2）考察每乙個子集，若發現某子集中的狀態不等價，將其劃分為兩個集合；
（3）重複第（2）步，繼續考察已得到的每乙個子集，直到沒有任何乙個子集需要繼續劃分為止。這時dfa的狀態被分成若干個互不相交的子集。
（4）從每個子集中選出乙個狀態做代表即可得到最簡的dfa。
三．程式分析
通過本設計所要求達到的目的是：充分理解和掌握nfa，dfa以及nfa確定化過程的相關概念和知識，理解和掌握子集法的相關知識和應用，現在需要程式設計實現對輸入nfa轉換成dfa輸出的功能。
程式總框圖如下：
功能圖如下：
4．執行結果
5. 實驗問題及心得
通過此次對從nfa到dfa的轉化和dfa的化簡的設計，使我更好的理解了nfa確定化過程的相關知識，很好的理解了子集法的演算過程。還有dfa的化簡過程有了更好地理解。經過多次試驗，在正確輸入相關資料的情況下，程式能正常執行，當錯誤操作或輸入錯誤資料時，程式將應錯誤自動關閉。
經過這次課程設計,也讓我深刻的認識到實踐才是最重要的。書本只能教給我們基礎知識,要怎樣運用,將那些知識真正吸收,轉化為自己的智慧型,只有通過實踐才能達到。編譯原理是一門實用性很強，對我們的專業很有幫助的科目,我將會繼續努力,不斷增加自己的知識面,把編譯原理學習的更好。
6. 附錄
#include
#include
#define maxs 100
using namespace std;
string node;//結點集合
string change;//終結符集合
int n;//nfa邊數
struct edge
;struct chan
;void kong(int a)
//排序
void paixu(string &a)
void eclouse(char c,string &he,edge b)
}void move(chan &he,int m,edge b)
//輸出
void outputfa(int len,int h,chan *t)
cout< }
}void main()
n=i;
/*for(j=0;j cout< 1 用excel編輯好乙個 然後點選 檔案 另存為web頁 web頁就是網頁檔案，在 儲存選項 處把 儲存整個工作簿 調整成 選擇 工作表 把預設檔名 根據實際情況改成你所需要的名字，如 彙總表.htm 再點選 儲存 注意，在改名時絕對不可以把後面的.htm去掉，只要改 前面的部分就可以了。2 找到... 如何把pdf檔案轉換成txt文件 現在是電子書的時代，很多朋友的電子裝置只支援txt格式的檔案，可是找到的一些不錯的書籍卻是pdf的格式。怎麼把pdf格式轉成txt格式呢？近來，總有朋友問我這個問題。這裡把我的方法寫下來，分享給朋友們，希望能幫到大家。更希望起到拋磚引玉的作用，有更好的方法被分享出來... 有時我們可能會因為工作的需要，將word轉excel裡面，或是把excel轉成word文件等，然而這幾種簡單的來回轉換方法你都能熟練的掌握嗎？今天word聯盟就來給大家演示下這兩種轉換的方法。word轉為excel 的方法 word轉excel就是將word中製作好的 轉成excel 可能是因為前期...如何把EXCEL轉換成
如何把pdf檔案轉換成
怎麼將轉為Excel,Excel轉換成