形式語言與自動機(jī)實驗報告

1、電子科技大學(xué)計算機(jī)學(xué)院標(biāo)準(zhǔn)實驗報告（實驗）課程名稱形式語言與自動機(jī)電子科技大學(xué)教務(wù)處制表技大學(xué) 報告 指導(dǎo)教師：吳婧瑾實驗時間：第七周周日下午電子科實驗學(xué)生姓名： 林怡 學(xué)號： 23實驗地點： 科研樓 A504一、實驗室名稱： 計算機(jī)學(xué)院軟件實驗室二、實驗項目名稱： 文法產(chǎn)生語言三、實驗學(xué)時： 6 學(xué)時四、實驗原理:1. 文法的存儲使用兩種方式存儲文法：程序方式與文件方式。程序方式是指文法的四元組均固化到程序內(nèi)，即一個程序只對應(yīng)于一個文法。文件方式是指將文法的四元組使用純文本方式進(jìn)行存儲，并定義好其格式。所設(shè)計的程序可處理任意的文法。2. 文法的表示使用面向?qū)ο蟪绦蛟O(shè)計語言可描述除文法的四元式

2、， 如： 采用字符數(shù)組表示其字母表和變量表， 字符表示開始符號， 字符串?dāng)?shù)組表示產(chǎn)生式組。 注意產(chǎn)生式 符號（即箭頭）在ASCII字符集中沒有，可采用來代替。人工經(jīng)常使用的， 通過產(chǎn)生式組獲得其它三元式的方式不可取， 因為需要約 定哪些是字母、哪些是變量，工作量很大，反而使其表示更復(fù)雜。3. 句子的產(chǎn)生根據(jù)給定的長度產(chǎn)生不大于該長度的所有串。兩種文法存儲方式均需要注意不同產(chǎn)生式可能有相同的左部， 如 S -> a 與 S -> aS。要生成所有句子則不同的產(chǎn)生式均需要使用，因此需要一個數(shù)組（或隊列、棧）來存儲當(dāng)前產(chǎn)生的句型。五、實驗?zāi)康?. 掌握文法的表示方法；2. 理解文法產(chǎn)生語

3、言的過程；3. 理解有窮文法可以產(chǎn)生無窮語言。六、實驗內(nèi)容1. 使用兩種方式存儲文法。2. 使用所表示文法產(chǎn)生所有長度不大于N 的串。七、實驗器材（設(shè)備、元器件） ：PC微機(jī)一臺八、實驗步驟給定文法Gi: S -> a, S -> aS與G2: S -> ab, S -> aSb （可替換為其它稍復(fù)雜的文法） 。進(jìn)行如下設(shè)計：1. 設(shè)計程序表示的文法G1 與 G2 及其推導(dǎo)句子的方式，并與手工運行結(jié)果進(jìn)行對比；2. 設(shè)計文法的存儲格式。 用 4 行文本表示四元式： 第一行為開始狀態(tài)S， 第二行為終極符，第三行為產(chǎn)生式，第四行為非終極符；3. 將文法從文件讀入內(nèi)存；4.

4、對于給定的字符串長度上限，獲得所有的句子；5. 進(jìn)行文法文件的合法性判定（如產(chǎn)生式中出現(xiàn)了既非字母，又非變量的符號） 。九、實驗數(shù)據(jù)及結(jié)果分析1. 當(dāng)輸入字符串長度為N=3 時，輸出文件result.txt 中共有三行字符串，分別為 ab, aabb, aaabbb ；2. 當(dāng)輸入字符串長度為N=5 時，輸出文件result.txt 中共有五行字符串，分 別為 ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb運行程序并輸入字符串長度圖二 文件輸出結(jié)果十、實驗結(jié)論1. 文法需要用四元式來表示；2. 文法的存儲方式不影響文法本身。十一、總結(jié)及心得體會通過本實驗的練習(xí)，熟

5、悉了文法的構(gòu)造方法，對文法的作用有進(jìn)一步理解；對抽象模型的實現(xiàn)方式有了整體的了解，進(jìn)一步提高了程序設(shè)計技術(shù)水平。十二、對本實驗過程及方法、手段的改進(jìn)建議1、 由于本實驗給定的文法比較簡單，產(chǎn)生式的右邊只包含一個非終極符，所以對于包含多個非終極符形如 S->ABab,AB->a,B->b 的文法不能很好的處理；2、 實驗中采用了類似深度優(yōu)先搜索的策略，對于文法：S -> ab, S -> aSb， S->Aa,A->a若給定字符串長度N=5 ，輸出文本中將只有形如 aaabbb 的結(jié)果輸出，而不會有由產(chǎn)生式 S->Aa 以及 A->a 所推導(dǎo)

6、出的句子。所以可以把實驗的要求改為給定文法能推導(dǎo)出的句子的長度，而不是輸出文本中所有字符串的長度。報告評分：指導(dǎo)教師簽字：技大學(xué) 報告 指導(dǎo)教師：吳婧瑾實驗時間：第八周周日下午電子科實驗學(xué)生姓名： 林怡 學(xué)號： 23實驗地點： 科研樓 A504一、實驗室名稱： 計算機(jī)學(xué)院軟件實驗室二、實驗項目名稱： DFA 對句子的識別三、實驗學(xué)時： 3 學(xué)時四、實驗原理DFA 對句子的線性識別。五、實驗?zāi)康?. 加深對 DFA 原理的理解。2. 學(xué)習(xí)使用Java進(jìn)行算法的實現(xiàn)。3. 掌握一定的圖形編程。六、實驗內(nèi)容理解 DFA 的工作原理，進(jìn)行如下幾個方面的設(shè)計與實現(xiàn)：1設(shè)計固定DFA。即將DFA使用if-

7、then-else,以及switch-case和for循環(huán)的方式表示。一個函數(shù)只能表示一個DFA ，而整個的程序只圍繞該DFA 進(jìn)行。2 設(shè)計文件形式存儲DFA 。 設(shè)計文件格式； 進(jìn)行 DFA 的動態(tài)生成； 使用一組字符串對所生成DFA 的有效性和正確性進(jìn)行驗證。3 圖形化的顯示。使用 Java 的圖形模塊進(jìn)行結(jié)果的顯示。七、實驗器材（設(shè)備、元器件）PC微機(jī)一臺八、實驗步驟1 .設(shè)計一個簡單的固定 DFA,觀察一個字符串使其達(dá)到的狀態(tài)序列，并與 手工運行結(jié)果進(jìn)行對比。2 .設(shè)計DFA的存儲格式。文本共五行，第一行為DFA所能接受的字符，第 二行為DFA的所有狀態(tài)，第三行為DFA的狀態(tài)轉(zhuǎn)移函數(shù)

8、（形如P0_0_P1）其含 義為狀態(tài)P0接受字符0到達(dá)狀態(tài)P1,第四行為DFA的開始狀態(tài)，最后一行為 DFA的終止?fàn)顟B(tài)（可能有多個）；3 .將DFA從文件讀入內(nèi)存，并使用對象進(jìn)行狀態(tài)的合適表示。4 .對于給定的字符用，跟蹤所經(jīng)過的狀態(tài)序列。九、實驗數(shù)據(jù)及結(jié)果分析圖1DFA狀態(tài)轉(zhuǎn)移圖圖2程序運行結(jié)果圖通過測試數(shù)據(jù)，基本驗證了算法實現(xiàn)的正確性。十一、總結(jié)及心得體會通過本實驗的練習(xí)，熟悉了 DFA 的基本工作原理，對使用 DFA 進(jìn)行構(gòu)造有 了直觀的認(rèn)識；對實現(xiàn)過程中的困難有了較深的體會。十二、對本實驗過程及方法、手段的改進(jìn)建議1、 本實驗中由于 DFA 只有一個終止?fàn)顟B(tài)， 所以可以進(jìn)一步考慮有多個

9、終止?fàn)顟B(tài)的情況；2、 同樣， 該 DFA 的狀態(tài)轉(zhuǎn)移函數(shù)也僅限于一個狀態(tài)與另一個狀態(tài)之間的轉(zhuǎn)移，對于多個狀態(tài)集之間的轉(zhuǎn)移情況也應(yīng)作考慮。報告評分：指導(dǎo)教師簽字：十、實驗結(jié)論技大學(xué) 報告 指導(dǎo)教師：吳婧瑾實驗時間：第九周周日下午電子科實驗學(xué)生姓名： 林怡 學(xué)號： 23實驗地點： 科研樓 A504一、實驗室名稱： 計算機(jī)學(xué)院軟件實驗室二、實驗項目名稱： NFA 對句子的識別三、實驗學(xué)時： 3 學(xué)時四、實驗原理NFA 對句子的非線性識別。五、實驗?zāi)康?. 加深對 NFA 原理的理解。2. 學(xué)習(xí)使用Java進(jìn)行算法的實現(xiàn)。3. 進(jìn)一步掌握圖形編程。六、實驗內(nèi)容理解 NFA 的工作原理，進(jìn)行如下幾個方面

10、的設(shè)計與實現(xiàn)：1 設(shè)計固定 NFA 與圖形文件形式存儲NFA 。2 使用 NFA 對字符串進(jìn)行判斷。3 圖形化的顯示。本內(nèi)容屬于擴(kuò)展要求。最好能進(jìn)行類似單步跟蹤的顯示，以便學(xué)生直觀地理解多條路徑的產(chǎn)生/ 消亡。七、實驗器材（設(shè)備、元器件）PC微機(jī)一臺八、實驗步驟1 .設(shè)計NFA的存儲格式。文本共五行，第一行為NFA所能接受的字符，第 二行為NFA的所有狀態(tài)，第三行為NFA的狀態(tài)轉(zhuǎn)移函數(shù)（形如P0_0_P1）其含 義為狀態(tài)P0接受字符0到達(dá)狀態(tài)P1,第四行為NFA的開始狀態(tài)，最后一行為NFA的終止?fàn)顟B(tài)（可能有多個）；2 .將NFA從文件讀入內(nèi)存，并使用對象進(jìn)行狀態(tài)的合適表示。3 .對于給定的字符

11、用，跟蹤所經(jīng)過的狀態(tài)序列。經(jīng)過的狀態(tài)序列。初始狀態(tài)下，只有一個活動狀態(tài)，即開始狀態(tài)。讀入一個 字符后，由于NFA的不確定性，可能導(dǎo)致有多個活動狀態(tài)。隨著字符的不斷讀 入，某些活動狀態(tài)的下一個狀態(tài)既可以有多個， 也可以一個也沒有。如果字符串 讀完時活動狀態(tài)集合包含了某些終止?fàn)顟B(tài)，則說明字符串被該NFA接受。九、實驗數(shù)據(jù)及結(jié)果分析圖1 NFA狀態(tài)轉(zhuǎn)移圖程序運行結(jié)果圖通過測試數(shù)據(jù)，基本驗證了算法實現(xiàn)的正確性。十一、總結(jié)及心得體會根據(jù)本實驗，理解了 NFA 的實際工作原理。實際上，對于一個字符串，由于處理過程中可能同時存在多個活動狀態(tài)，其所耗費時間相當(dāng)多。十二、對本實驗過程及方法、手段的改進(jìn)建議本實驗

12、中的NFA為不帶空移動的NFA,可以進(jìn)一步考慮帶空移動的e -NFA如何實現(xiàn)。報告評分：指導(dǎo)教師簽字：技大學(xué) 報告 指導(dǎo)教師：吳婧瑾實驗時間：第十周周日下午電子科實驗學(xué)生姓名： 林怡 學(xué)號： 23實驗地點： 科研樓 A504一、實驗室名稱： 計算機(jī)學(xué)院軟件實驗室二、實驗項目名稱： NFA 向 DFA 的轉(zhuǎn)化三、實驗學(xué)時： 4 學(xué)時四、實驗原理NFA 的一個狀態(tài)子集可以用 DFA 的一個狀態(tài)表示。五、實驗?zāi)康?. 加深對 NFA 和 DFA 等價性的理解。2. 學(xué)習(xí)使用Java進(jìn)行算法的實現(xiàn)。3. 進(jìn)一步掌握圖形編程。六、實驗內(nèi)容理解 NFA 向 DFA 的轉(zhuǎn)化的原理，進(jìn)行如下幾個方面的設(shè)計與實

13、現(xiàn)：1 據(jù)文件形式存儲NFA 獲得轉(zhuǎn)移函數(shù)。在實驗五的基礎(chǔ)上， NFA 的狀態(tài)轉(zhuǎn)移函數(shù)比較容易獲得。2根據(jù) NFA 狀態(tài)轉(zhuǎn)移函數(shù)構(gòu)造相應(yīng)DFA 的狀態(tài)轉(zhuǎn)移函數(shù)。 這是本實驗的重點。一個有n個狀態(tài)的NFA轉(zhuǎn)化后的DFA最多有2n個狀態(tài)，因此表的最大長度 為2n。由于多個狀態(tài)是無用狀態(tài)，在轉(zhuǎn)化過程中并不需要為其進(jìn)行計算。如 何避免無效的計算，同時保證轉(zhuǎn)換過程的正確性是本實驗的難點。3 生成相應(yīng)的DFA 。在實驗三的基礎(chǔ)上，這一方面的功能不會太難。但要注意終止?fàn)顟B(tài)的設(shè)定。七、實驗器材（設(shè)備、元器件）PC微機(jī)一臺八、實驗步驟1. 設(shè)計一個方法（函數(shù)） ，它可以根據(jù)NFA 獲得其狀態(tài)轉(zhuǎn)移函數(shù)。2. 設(shè)計

14、一個方法， 它可以將 NFA 的狀態(tài)轉(zhuǎn)移函數(shù)轉(zhuǎn)換為 DFA 的狀態(tài)轉(zhuǎn)移函 數(shù)。3. 在上一步的基礎(chǔ)上，設(shè)計一個方法，它可以在轉(zhuǎn)換過程中盡量避免無效 的計算。4. 根據(jù)DFA 的狀態(tài)轉(zhuǎn)移函數(shù)，進(jìn)行DFA 的內(nèi)部表示。5. 根據(jù)DFA 的內(nèi)部表示，寫入相應(yīng)的文件，以便下次從該文件重新讀取并構(gòu)建 DFA 。6. 使用一組字符串，驗證生成的DFA與原始的NFA是否等價。同時根據(jù)手 工轉(zhuǎn)換的方式檢查自動轉(zhuǎn)換程序是否正確。九、實驗數(shù)據(jù)及結(jié)果分析1 程序運行結(jié)果圖圖 2 生成的 DFA 文件將文件 dfa.txt 的內(nèi)容復(fù)制到實驗二DFA 的程序目錄下，執(zhí)行結(jié)果如圖：圖三 DFA 程序檢驗圖十、實驗結(jié)論通過測試數(shù)據(jù)，基本驗證了算法實現(xiàn)的正確性。十一、總結(jié)及心得體會根據(jù)本實驗，進(jìn)一步理解了 NFA與DFA的等價性。在NFA轉(zhuǎn)換為DFA時,如果某些狀態(tài)下無輸入，可以在DFA 中增加陷阱狀態(tài)來表示該情況下的狀態(tài)轉(zhuǎn)移函數(shù)。十二、對本