編譯原理作業(yè)集修訂

1、第三章 詞法分析本章要點(diǎn)詞法分析器設(shè)計(jì)，正規(guī)表達(dá)式與有限自動(dòng)機(jī)，詞法分析器自動(dòng)生成。本章目標(biāo)：理解對(duì)詞法分析器的任務(wù)，掌握詞法分析器的設(shè)計(jì)；掌握正規(guī)表達(dá)式與有限自動(dòng)機(jī)；掌握詞法分析器的自動(dòng)產(chǎn)生。本章重點(diǎn)：1詞法分析器的作用和接口，用高級(jí)語言編寫詞法分析器等內(nèi)容，它們與詞法分析器的實(shí)現(xiàn)有關(guān)。應(yīng)重點(diǎn)掌握詞法分析器的任務(wù)與設(shè)計(jì)，狀態(tài)轉(zhuǎn)換圖等內(nèi)容。2掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的技巧、方法或算法。（1）非形式描述的語言 « 正規(guī)式（2）正規(guī)式 ® NFA（非確定的有限自動(dòng)機(jī)）（3）NFA ® DFA（確定的有限自動(dòng)機(jī)）（4）DFA ® 最簡DFA本章難點(diǎn)

2、（1） 非形式描述的語言 « 正規(guī)式（2） 正規(guī)式 ® NFA（非確定的有限自動(dòng)機(jī)）（3） NFA ® DFA（確定的有限自動(dòng)機(jī)）（4） DFA ® 最簡DFA作業(yè)題一、單項(xiàng)選擇題（按照組卷方案，至少15道）1. 程序語言下面的單詞符號(hào)中， 一般不需要超前搜索a. 關(guān)鍵字 b. 標(biāo)識(shí)符 c. 常數(shù) d. 算符和界符2. 在狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)中， 一般對(duì)應(yīng)一個(gè)循環(huán)語句a. 不含回路的分叉結(jié)點(diǎn) b. 含回路的狀態(tài)結(jié)點(diǎn) c. 終態(tài)結(jié)點(diǎn) d. 都不是3. 用了表示字母，d表示數(shù)字，å=l，d，則定義標(biāo)識(shí)符的正則表達(dá)式可以是： 。(a)ld* (b)ll*

3、 (c)l(l | d)* (d)ll* | d*4. 正規(guī)表達(dá)式(|a|b)2表示的集合是 (a)，ab，ba，aa，bb (b)ab，ba，aa，bb(c)a，b，ab，aa，ba，bb (d)，a，b，aa，bb，ab，ba5. 有限狀態(tài)自動(dòng)機(jī)可用五元組（VT，Q，q0，Qf）來描述，設(shè)有一有限狀態(tài)自動(dòng)機(jī)M的定義如下：VT=0， 1，Q=q0， q1， q2，Qf=q2，的定義為：（q0，0）=q1（q1，0）=q2（q2，1）=q2 （q2，0）=q2M所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖為 。6. 有限狀態(tài)自動(dòng)機(jī)可用五元組（VT，Q，q0，Qf）來描述，設(shè)有一有限狀態(tài)自動(dòng)機(jī)M的定義如下：VT=0， 1

4、，Q=q0， q1， q2，Qf=q2，的定義為：（q0，0）=q1（q1，0）=q2（q2，1）=q2 （q2，0）=q2M所能接受的語言可以用正則表達(dá)式表示為 。(0|1)* 00(0|1)* (0|1)*00 0(0|1)*07 . 有限狀態(tài)自動(dòng)機(jī)可用五元組（VT，Q，q0，Qf）來描述，設(shè)有一有限狀態(tài)自動(dòng)機(jī)M的定義如下：VT=0， 1，Q=q0， q1， q2，Qf=q2，的定義為：（q0，0）=q1（q1，0）=q2（q2，1）=q2 （q2，0）=q2M所能接受的語言為 。由0和1所組成的符號(hào)串的集合以0為頭符號(hào)和尾符號(hào)、由0和1所組成的符號(hào)串的集合以兩個(gè)0結(jié)束的，由0和1所組成的

5、符號(hào)串的集合以兩個(gè)0開始的，由0和1所組成的符號(hào)串的集合8. 從接受語言的能力上來說，非確定型有窮自動(dòng)機(jī)和_是等價(jià)的。a. .正規(guī)式；.上下文無關(guān)文法；.確定性有窮自動(dòng)機(jī)；b. .左線性正規(guī)文法；.右線性正規(guī)文法；.確定性有窮自動(dòng)機(jī)；c. .正規(guī)式；.上下文無關(guān)文法；.正規(guī)文法；d. .正規(guī)式；.確定性有窮自動(dòng)機(jī)；.下推自動(dòng)機(jī)；9. 下面四個(gè)選項(xiàng)中，關(guān)于編譯過程中掃描器的任務(wù)的敘述，_是較為完整且正確的。組織源程序的輸入；按詞法規(guī)則分割出單詞，識(shí)別其屬性，并轉(zhuǎn)換成屬性字的形式輸出；刪除注釋；刪除空格和無用字符；行計(jì)數(shù)、列計(jì)數(shù)；發(fā)現(xiàn)并定位詞法錯(cuò)誤；建立符號(hào)表。按詞法規(guī)則分割出單詞，識(shí)別其屬性，并

6、轉(zhuǎn)換成屬性字的形式輸出；發(fā)現(xiàn)并定位詞法錯(cuò)誤；建立符號(hào)表；輸出狀態(tài)轉(zhuǎn)換圖；把狀態(tài)轉(zhuǎn)換圖自動(dòng)轉(zhuǎn)換成詞法掃描程序。組織源程序的輸入；按詞法規(guī)則分割出單詞，識(shí)別其屬性，并轉(zhuǎn)換成屬性字的形式輸出。組織源程序的輸入；按詞法規(guī)則分割出單詞，識(shí)別其屬性，并轉(zhuǎn)換成屬性字的形式輸出；行計(jì)數(shù)、列計(jì)數(shù)；發(fā)現(xiàn)并定位詞法錯(cuò)誤；建立符號(hào)表；輸出狀態(tài)轉(zhuǎn)換圖；把狀態(tài)轉(zhuǎn)換圖自動(dòng)轉(zhuǎn)換成詞法掃描程序。10. 關(guān)于NFA的敘述中，下面_是不正確的。 A.有一個(gè)有窮字母表 B.有多個(gè)初始狀態(tài) C.有多個(gè)終止?fàn)顟B(tài) D.有多個(gè)有限狀態(tài)11. 詞法分析的理論基礎(chǔ)是 。'#Q;#f,G6aA.有窮自動(dòng)機(jī)理論 B.圖靈機(jī)理論.圖論.無窮自

7、動(dòng)機(jī)理論12. 設(shè)有兩個(gè)狀態(tài)S和T，如果從S出發(fā)能讀出某個(gè)字w而停于終態(tài)，那么從T出發(fā)也能讀出同樣的字而停于終態(tài)；反之，果從T出發(fā)能讀出某個(gè)字w而停于終態(tài)，那么從S出發(fā)也能讀出同樣的字而停于終態(tài)。則我們稱狀態(tài)S和狀態(tài)T是 。A. 可區(qū)分的；B. 等價(jià)的；C. 多余的；D. 無用的。13. 詞法分析器的輸出結(jié)果是 。A、單詞自身值B、單詞在符號(hào)表中的位置C、單詞的種別編碼D、單詞的種別編碼和自身值14. 編譯過程中掃描器的任務(wù)包括_。組織源程序的輸入按詞法規(guī)則分割出單詞，識(shí)別出其屬性，并轉(zhuǎn)換成屬性字的形式輸出刪除注解刪除空格及無用字符行計(jì)數(shù)、列計(jì)數(shù)發(fā)現(xiàn)并定位詞法錯(cuò)誤建立符號(hào)表a b c d15.

8、 下述正則表達(dá)式中_與(a*+b)*(c+d)等價(jià)(即有相同符號(hào)串集)。(x+y亦可寫作x|y)a*(c+d)+b(c+d)a*(c+d)*+b(c+d)*a*(c+d)+b(c+d)(a+b)*c+(a+b)*d(a*+b)*c+(a*+b)*da. b. c. d. 16、正則式的“*”讀作_。a，并且 L或者 c連接 d閉包17. 在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表 ，用圓圈表示。 a.輸入緩沖區(qū) b.向前搜索 c.狀態(tài) d.字符串18. 與(a|b)*(a|b)等價(jià)的正規(guī)式是 。A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D. (a|b)*19.無符號(hào)常數(shù)的識(shí)

9、別和拼數(shù)工作通常都在 階段完成。.!u$&#Y"b4q詞法分析語法分析語義分析代碼生成一答案：1. b；2. b；3. c；4. d；5.；6. ，7.；8. b；9. ；10. B；11. A；12. B；13. d；14. d；15.d；16.d；17.c；18. C；19. A二、填空題：（按照組卷方案，至少15道）1. 詞法分析器對(duì)掃描緩沖區(qū)進(jìn)行掃描時(shí)一般用兩個(gè)指示器，一個(gè)_；另一個(gè)_。2. 一個(gè)確定性有限自動(dòng)機(jī)DFA M的化簡是指：尋找一個(gè)狀態(tài)數(shù)比M少的DFA M，使得 。3. 詞法分析器所的輸出常表示成如下形式的二元式：（_，_）。4. 一個(gè)狀態(tài)轉(zhuǎn)換圖只包含有限個(gè)

10、狀態(tài)，其中有一個(gè)被認(rèn)為是_，而且實(shí)際上至少有一個(gè)_。5. 把狀態(tài)轉(zhuǎn)換圖用程序?qū)崿F(xiàn)時(shí)，對(duì)于含有回路的狀態(tài)結(jié)點(diǎn)來說，可以讓它對(duì)應(yīng)一個(gè)_程序段。6. 詞法分析階段的任務(wù)式從左到右掃描 ，從而逐個(gè)識(shí)別 。7. 如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那么，對(duì)于這個(gè)單詞符號(hào)， 就可以完全代表它自身了。8. 單詞符號(hào)的屬性值是指單詞符號(hào)的特性或特征，其屬性值則是反映特性或特征的值。比如，對(duì)于某個(gè)標(biāo)識(shí)符，常將 作為其屬性值。9. 單詞符號(hào)的屬性值是指單詞符號(hào)的特性或特征，其屬性值則是反映特性或特征的值。比如，對(duì)于常數(shù)，常將 作為其屬性值。10. 如果一個(gè)種別含有多個(gè)單詞符號(hào)，那么，對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別

11、編碼以外，還應(yīng)給出有關(guān) 。11. 如果 ，則認(rèn)為這兩個(gè)正規(guī)式等價(jià)。12. 對(duì)于S*中的任何符號(hào)串a(chǎn)，如果存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且 ，則稱a被該自動(dòng)機(jī)所接受（識(shí)別）。13. 一個(gè)Lex源程序主要包括兩部分，一部分是 ，另一部分是 。14. 一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示 ，列表示 ，矩陣元素表示 。這個(gè)矩陣叫狀態(tài)轉(zhuǎn)換矩陣。15. 對(duì)于詞法分析程序來說，當(dāng)程序到達(dá)“錯(cuò)誤處理”時(shí)，意味著現(xiàn)行狀態(tài)i和當(dāng)前所面臨的輸入串不匹配。如果后面還有狀態(tài)圖，出現(xiàn)在這個(gè)地方的代碼應(yīng)該為： 。二答案：1. 指向當(dāng)前正在識(shí)別的單詞符號(hào)的開始位置，用于向前搜索以尋找單詞符號(hào)的終點(diǎn)；2. L(

12、M)=L(M')；3. 單詞種別，單詞符號(hào)的屬性值；4. 初態(tài)，終態(tài)；5. 由while和if語句構(gòu)成的；6. 源程序，單詞；7. 種別編碼；8. 存放它的有關(guān)信息的符號(hào)表項(xiàng)的指針；9. 存放它的常數(shù)表項(xiàng)的指針；10. 單詞符號(hào)的屬性信息（屬性值）；11. 兩個(gè)正規(guī)式所表示的正規(guī)集相同；12. 這條通路上所有弧的標(biāo)記符號(hào)連接起來形成的符號(hào)串等于a；13. 正規(guī)定義式，識(shí)別規(guī)則；14. 狀態(tài)，輸入字符，轉(zhuǎn)換函數(shù)（或d(s, a)）的值；15. 將搜索器回退一個(gè)位置，并令下一個(gè)狀態(tài)圖開始工作。三、判斷題：（按照組卷方案，至少15道）1NFA M的非確定性表現(xiàn)在它有多個(gè)終態(tài)。 （ ）2. 有

13、窮自動(dòng)機(jī)接受的語言是正則語言。 （ ）3. 若r1和r2是上的正規(guī)式，則r1|r2也是。 （ ）4. 設(shè)M是一個(gè)NFA，并且L(M)x， y， z，則M的狀態(tài)數(shù)至少為4個(gè)。 （ ）5. 令a， b，則上所有以b為首的字符構(gòu)成的正規(guī)集的正規(guī)式為b*(a|b)*。（ ）6. 對(duì)任何一個(gè)NFA M，都存在一個(gè)DFA M'，使得L(M')=L(M)。（ ）7. 對(duì)一個(gè)右線性文法G，必存在一個(gè)左線性文法G'，使得L(G)=L(G')，反之亦然。（ ）8. 對(duì)任意一個(gè)右線性文法G，都存在一個(gè)NFA M，滿足L(G)=L(M)。 ( )9. 對(duì)任意一個(gè)右線性文法G，都存在一個(gè)

14、DFA M，滿足L(G)=L(M)。 ( )10. 對(duì)任何正則表達(dá)式r，都存在一個(gè)NFA M，滿足L(M)=L(r)。 ( )11. 對(duì)任何正則表達(dá)式r，都存在一個(gè)DFA M，滿足L(M)=L(r)。 ( ) 12一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。（  ）13. 一個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)有限狀態(tài)自動(dòng)機(jī)； （ ）14. 在詞法分析的狀態(tài)轉(zhuǎn)換圖中，有些結(jié)點(diǎn)是帶星號(hào)的，這些結(jié)點(diǎn)肯定是終態(tài)結(jié)點(diǎn)。（ ）15. 適當(dāng)設(shè)置掃描緩沖區(qū)的大?。ū热缛菁{256個(gè)字符）可以保證單詞符號(hào)不會(huì)被它的邊界所打斷。 （ ）四答案：1. ×；2. Ö；3. &#

15、214;；4. ×；5. ×；6. Ö；7. Ö；8. Ö；9. Ö；10. Ö；11. Ö；12×；13. ×；14. Ö；15. ×；四、名詞解釋：（按照組卷方案，至少5道）1. 狀態(tài)轉(zhuǎn)換圖；2. 正規(guī)式（正規(guī)表達(dá)式、正則表達(dá)式）的形式化定義；3. 給出確定性有限狀態(tài)自動(dòng)機(jī)的形式化定義；4. 給出非確定性有限狀態(tài)自動(dòng)機(jī)的形式化定義；5. DFA狀態(tài)最小化。四答案1. 狀態(tài)轉(zhuǎn)換圖是一張有限方向圖，用于識(shí)別（或接受）一定的字符串。在圖中，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示；狀態(tài)之間用箭

16、弧連結(jié)；箭弧上的標(biāo)記（字符）代表在射出結(jié)點(diǎn)（即箭弧的始結(jié)點(diǎn)）狀態(tài)下可能出現(xiàn)的字符或字符類。一張狀態(tài)轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)（即有限個(gè)結(jié)點(diǎn)），其中一個(gè)被認(rèn)為是初態(tài)，而且實(shí)際上至少要有一個(gè)終態(tài)（用雙圈表示）。2. 正規(guī)式是采用遞歸方式來定義的。（1）e和Æ都是正規(guī)式；（2）任何aå，a是å上的一個(gè)正規(guī)式；（3）假定r和s都是å上的正規(guī)式，則r|s、r×s、和r*也都是正規(guī)式。3. 一個(gè)確定有限自動(dòng)機(jī)（DFA）M是一個(gè)五元式：M=(S，å，d，s0，F(xiàn))，其中：（1）S是一個(gè)有限集合，它的每一個(gè)元素稱為一個(gè)狀態(tài)；（2）å是一個(gè)有限字

17、母表，它的每一個(gè)元素稱為一個(gè)輸入字符；（3）d是一個(gè)從S×å到S的單值部分映射。d(s，a)=s'，意思是：當(dāng)前狀態(tài)是s，輸入字符為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)入下一個(gè)狀態(tài)s'。 s'稱為s的后繼狀態(tài)；（4）s0S，是自動(dòng)機(jī)的惟一初態(tài)；（5）FÍS，是一個(gè)終態(tài)集合。一個(gè)非確定有限自動(dòng)機(jī)（NFA）M是一個(gè)五元式：M=(S，å，d，s0，F(xiàn))，其中：（1）S是一個(gè)有限集合，它的每一個(gè)元素稱為一個(gè)狀態(tài)；（2）å是一個(gè)有限字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；（3）d是一個(gè)從S×å到S的子集的映射。d(s，a)=s1，

18、s2，sm，意思是：當(dāng)前狀態(tài)是s，輸入字符為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)入的下一個(gè)狀態(tài)可能是s1，或者s2，或者sm； （4）s0S，是自動(dòng)機(jī)的惟一初態(tài)；（5）FÍS，是一個(gè)終態(tài)集合。五、簡答題：（按照組卷方案，至少5道）1 寫出標(biāo)識(shí)符（以字母打頭，由字母和數(shù)字組成的符號(hào)串）的正則表達(dá)式。答：letter®A ½B ½. Z ½ a ½b ½. ½zdigit ®0 ½1 ½. ½9id ® letter(letter½digit)*2. 詞法分析器對(duì)程序語言的單詞符

19、號(hào)一般如何分類？答：程序語言的單詞符號(hào)一般可以分為下列五種：（1）關(guān)鍵字：是有程序語言所定義的具有固定意義的標(biāo)識(shí)符，有時(shí)也稱保留字或基本字；（2）標(biāo)識(shí)符：用來表示變量名、數(shù)組名和過程名等各種名字；（3）常數(shù)：一般有整型、實(shí)型、布爾型和文字型等各種類型，是程序執(zhí)行過程中不變的量；（4）運(yùn)算符：如、*、/等各種進(jìn)行算術(shù)邏輯運(yùn)算的符號(hào)；（5）界符：如逗號(hào)、分號(hào)、括號(hào)等。3. 人運(yùn)狼、羊、菜過河，一次運(yùn)一件，不讓羊吃掉菜，也不讓狼吃掉羊，畫出渡河的狀態(tài)轉(zhuǎn)換圖。可否將其抽象為一個(gè)有限自動(dòng)機(jī)？3. 先寫出渡河的方法，串中對(duì)象順序?yàn)槿藖砘囟珊訒r(shí)所運(yùn)的貨物的順序：羊空菜羊狼空羊；羊空狼羊菜空羊現(xiàn)給出一個(gè)NFA

20、: M=(，Q，0，9，)其中=羊，空，菜，狼，Q=0，1，2，3，4，5，6，7，8，9，轉(zhuǎn)形函數(shù)：(0，羊)=1，(1，空)=2，(2，菜)=3，(2，狼)=5(3，羊)=4，(5，羊)=6，(4，狼)=7，(6，菜)=7(7，空)=8，(8，羊)=94 C語言無符號(hào)實(shí)數(shù)用正則表達(dá)式怎么定義？答：digit ®0 ½1 ½. ½9digits ®digit(digit)*fraction ® . digits exponent ®E (+ ½- e½) digits )num ® digit

21、s ( fraction | e ) (exponent | e )5. 分析下面各正規(guī)表達(dá)式所表示的語言。(1) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答：(1) |0，1*，中有偶數(shù)個(gè)0和偶數(shù)個(gè)1，即由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的串。6. 何謂掃描器？掃描器的功能是什么？答：掃描器就是詞法分析器，它接受輸入的源程序，對(duì)源程序進(jìn)行詞法分析，識(shí)別出一個(gè)個(gè)的單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。一般把詞法分析器安排成一個(gè)子程序，每當(dāng)語法分析器需要一個(gè)單詞符號(hào)時(shí)就調(diào)用這個(gè)子程序。每一次調(diào)用，詞法分析器就從輸入串中識(shí)別出一個(gè)單詞符號(hào)，把它交給語法分析

22、器。詞法分析器工作的第一步是輸入源程序文本。輸入串中一般都包含一些沒有意義的字符，如：空白符、跳格符、回車符和換行符等編輯性字符除了出現(xiàn)在文字常數(shù)中之外，在別處的任何出現(xiàn)都沒有意義，而注解部分幾乎允許出現(xiàn)在程序中的任何地方。它們不是程序的必要組成部分，預(yù)處理時(shí)可以將其剔掉。詞法分析器一般會(huì)構(gòu)造一個(gè)預(yù)處理子程序來處理上述任務(wù)。7. 試簡述有窮狀態(tài)自動(dòng)機(jī)與正則表達(dá)式的等價(jià)性概念。答：上的非確定有限自動(dòng)機(jī)M所能識(shí)別字的全體L(M)是上的一個(gè)正規(guī)集；同時(shí)，對(duì)于上的每個(gè)正規(guī)集V，存在一個(gè)上的確定有限自動(dòng)機(jī)M，使得V=L(M)。六、應(yīng)用題：1. 有一個(gè)語言，它接收=0，1上所有滿足如下條件的字符串：每個(gè)1

23、都有0直接跟在右邊。（）給出該語言的正規(guī)式（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化解法1：（）按題意相應(yīng)的正規(guī)表達(dá)式是0*(0 | 10)*0*或0*( 100*)*0*。（）構(gòu)造NFA為0*的NFA為：0 | 10的NFA為：(0 | 10)*的NFA為：0*(0 | 10)*0*的NFA為（給各個(gè)結(jié)點(diǎn)標(biāo)上序號(hào)）（）用子集法確定化II0I10，1，3，4，5，6，9，13，14，15，17=1，2，3，4，5，6，9，13，14，15，175，7，8，9，13，14，15，1715，16，171，2，3，4，5，6，7，8，9，13，14，15，

24、16，17=10，111，2，3，4，5，6，7，8，9，13，14，15，16，17，同上同上10，115，6，8，9，12，13，14，15，17Æ5，6，8，9，12，13，14，15，175，6，7，8，9，13，14，15，16，17舊態(tài)5，6，7，8，9，13，14，15，16，17舊態(tài)舊態(tài)令：0，1，3，4，5，6，9，13，14，15，17A；1，2，3，4，5，6，7，8，9，13，14，15，16，17B；10，11C；5，6，8，9，12，13，14，15，17D；5，6，7，8，9，13，14，15，16，17E；畫出DFA如圖所示：（）對(duì)該DFA進(jìn)行狀態(tài)最小

25、化PI(1)，I(2)C，A，B，D，EI(1)C不可再分；看I(2)A，B，D，E：A，B，D，E0B，E，落入了I(2)；A，B，D，E1C，落入了I(1)；所以，A，B，D，E是等價(jià)狀態(tài)，不再分；因此，從A，B，D，E中抽取一個(gè)狀態(tài)作為代表，C不變，得到簡化了的DFA如圖所示：解法2：（）構(gòu)造NFA為（3）用子集法確定化II0I1S01X，0，1，3，Y0，1，3，Y21，3，Y0，1，3，Y0，1，3，Y1，3，Y1，3，Y22/212342244333DFA為：（）可最小化，終態(tài)組為A，B，D，非終態(tài)組為C；A，B，D0A，B，D，A，B，D1C，所以A，B，D為等價(jià)狀態(tài)，可合并。2

26、. 已知字母表S = a， b上語言L = w | w中a的個(gè)數(shù)是偶數(shù)。（）給出該語言的正規(guī)式（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化2解法1：（） 語言L的正規(guī)式是：(a b*a | b)* 或 b*(a b*a b*)* （）畫出接收該語言的NFA（3）NFA轉(zhuǎn)換成DFAIIaIbSaB1，2，3，12，13=4，5，6，8，92，3，11，12，13，14ABC4，5，6，8，92，3，10，11，12，136，7，8，9BDE2，3，11，12，13，14=4，5，6，8，92，3，11，12，13，14CBC2，3，10，11，12，13

27、=4，5，6，8，92，3，11，12，13，14DBC6，7，8，92，3，10，11，12，136，7，8，9EDE得到的DFA為：（）對(duì)該DFA進(jìn)行狀態(tài)最小化PI(1)，I(2) B，E ，A，C，D B，E aD，落入I(2)中； B，E bE；落入I(1)中；I(1) B，E 不必再分。I(2)A，C，D aB，落入I(1)中；I(2)A，C，D bC，落入I(2)中；I(2)A，C，D 不必再分。故，得到的接受該語言的最簡DFA是：解法2（）畫出接收該語言的NFA（3）NFA轉(zhuǎn)換成DFAIIaIbSaB1，3=21，3ABA21，3=2BAB得到的DFA如下：（）對(duì)該DFA進(jìn)行狀態(tài)

28、最小化無法再分。3. 有一個(gè)語言，它接收=0，1上的含奇數(shù)個(gè)1的所有串。（）給出該語言的正規(guī)式（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化提示：正則表達(dá)式為0*1 (0|10*1)*。4. 已知=0，1上正則表達(dá)式為0(0|1)*0，（）該正則表達(dá)式所定義的語言是什么？（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化提示：(1) 以0開頭并且以0結(jié)尾的，由0和1組成的符號(hào)串。5已知=0，1上正則表達(dá)式為(0|1)*0(0|1)(0|1)，（）該正則表達(dá)式所定義的語言是什么？（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)

29、換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化提示：(1) 由0和1組成的符號(hào)串，且從右邊開始數(shù)第3位為0。6已知=0，1上正則表達(dá)式為0*10*10*10*，（）該正則表達(dá)式所定義的語言是什么？（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化提示：(1) 含3個(gè)1的由0和1組成的符號(hào)串。  |0，1+，且中含有3個(gè)1 。7有一個(gè)語言，它接收=a，b上所有滿足如下條件的字符串：不含子串a(chǎn)bb的由a和b組成的符號(hào)串的全體。（）給出該語言的正規(guī)式（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化提示：正則表達(dá)式為：b*(a*|(ba)*)*。8 已知=0，1上正則表達(dá)式為(|0)1*)*，（）該正則表達(dá)式所定義的語言是什么？（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化提示：(1)由0和1組成的符號(hào)串。9已知=0，1上正則表達(dá)式為(a*|b*)*，（）該正則表達(dá)式所定義的語言是什么？（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價(jià)的DFA（）對(duì)該DFA進(jìn)行狀態(tài)最小化提示：(1)所有由a和