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

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

2、（1） 非形式描述的語言 « 正規(guī)式（2） 正規(guī)式 ® NFA（非確定的有限自動機(jī)）（3） NFA ® DFA（確定的有限自動機(jī)）（4） DFA ® 最簡DFA作業(yè)題一、單項選擇題（按照組卷方案，至少15道）1. 程序語言下面的單詞符號中， 一般不需要超前搜索a. 關(guān)鍵字 b. 標(biāo)識符 c. 常數(shù) d. 算符和界符2. 在狀態(tài)轉(zhuǎn)換圖的實現(xiàn)中， 一般對應(yīng)一個循環(huán)語句a. 不含回路的分叉結(jié)點 b. 含回路的狀態(tài)結(jié)點 c. 終態(tài)結(jié)點 d. 都不是3. 用了表示字母，d表示數(shù)字，å=l，d，則定義標(biāo)識符的正則表達(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)自動機(jī)可用五元組（VT，Q，q0，Qf）來描述，設(shè)有一有限狀態(tài)自動機(jī)M的定義如下：VT=0， 1，Q=q0， q1， q2，Qf=q2，的定義為：（q0，0）=q1（q1，0）=q2（q2，1）=q2 （q2，0）=q2M所對應(yīng)的狀態(tài)轉(zhuǎn)換圖為 。6. 有限狀態(tài)自動機(jī)可用五元組（VT，Q，q0，Qf）來描述，設(shè)有一有限狀態(tài)自動機(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)自動機(jī)可用五元組（VT，Q，q0，Qf）來描述，設(shè)有一有限狀態(tài)自動機(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所組成的符號串的集合以0為頭符號和尾符號、由0和1所組成的符號串的集合以兩個0結(jié)束的，由0和1所組成的

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

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

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

8、 下述正則表達(dá)式中_與(a*+b)*(c+d)等價(即有相同符號串集)。(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é)點代表 ，用圓圈表示。 a.輸入緩沖區(qū) b.向前搜索 c.狀態(tài) d.字符串18. 與(a|b)*(a|b)等價的正規(guī)式是 。A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D. (a|b)*19.無符號常數(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. 詞法分析器對掃描緩沖區(qū)進(jìn)行掃描時一般用兩個指示器，一個_；另一個_。2. 一個確定性有限自動機(jī)DFA M的化簡是指：尋找一個狀態(tài)數(shù)比M少的DFA M，使得 。3. 詞法分析器所的輸出常表示成如下形式的二元式：（_，_）。4. 一個狀態(tài)轉(zhuǎn)換圖只包含有限個

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

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

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

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

14、DFA M，滿足L(G)=L(M)。 ( )10. 對任何正則表達(dá)式r，都存在一個NFA M，滿足L(M)=L(r)。 ( )11. 對任何正則表達(dá)式r，都存在一個DFA M，滿足L(M)=L(r)。 ( ) 12一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)，最多只有一個終態(tài)。（  ）13. 一個正規(guī)式只能對應(yīng)一個有限狀態(tài)自動機(jī)； （ ）14. 在詞法分析的狀態(tài)轉(zhuǎn)換圖中，有些結(jié)點是帶星號的，這些結(jié)點肯定是終態(tài)結(jié)點。（ ）15. 適當(dāng)設(shè)置掃描緩沖區(qū)的大?。ū热缛菁{256個字符）可以保證單詞符號不會被它的邊界所打斷。 （ ）四答案：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)自動機(jī)的形式化定義；4. 給出非確定性有限狀態(tài)自動機(jī)的形式化定義；5. DFA狀態(tài)最小化。四答案1. 狀態(tài)轉(zhuǎn)換圖是一張有限方向圖，用于識別（或接受）一定的字符串。在圖中，結(jié)點代表狀態(tài)，用圓圈表示；狀態(tài)之間用箭

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

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

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

19、號一般如何分類？答：程序語言的單詞符號一般可以分為下列五種：（1）關(guān)鍵字：是有程序語言所定義的具有固定意義的標(biāo)識符，有時也稱保留字或基本字；（2）標(biāo)識符：用來表示變量名、數(shù)組名和過程名等各種名字；（3）常數(shù)：一般有整型、實型、布爾型和文字型等各種類型，是程序執(zhí)行過程中不變的量；（4）運(yùn)算符：如、*、/等各種進(jìn)行算術(shù)邏輯運(yùn)算的符號；（5）界符：如逗號、分號、括號等。3. 人運(yùn)狼、羊、菜過河，一次運(yùn)一件，不讓羊吃掉菜，也不讓狼吃掉羊，畫出渡河的狀態(tài)轉(zhuǎn)換圖?？煞駥⑵涑橄鬄橐粋€有限自動機(jī)？3. 先寫出渡河的方法，串中對象順序為人來回渡河時所運(yùn)的貨物的順序：羊空菜羊狼空羊；羊空狼羊菜空羊現(xiàn)給出一個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語言無符號實數(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ù)個0和偶數(shù)個1，即由偶數(shù)個0和偶數(shù)個1構(gòu)成的串。6. 何謂掃描器？掃描器的功能是什么？答：掃描器就是詞法分析器，它接受輸入的源程序，對源程序進(jìn)行詞法分析，識別出一個個的單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。一般把詞法分析器安排成一個子程序，每當(dāng)語法分析器需要一個單詞符號時就調(diào)用這個子程序。每一次調(diào)用，詞法分析器就從輸入串中識別出一個單詞符號，把它交給語法分析

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

23、都有0直接跟在右邊。（）給出該語言的正規(guī)式（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價的DFA（）對該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為（給各個結(jié)點標(biā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如圖所示：（）對該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是等價狀態(tài)，不再分；因此，從A，B，D，E中抽取一個狀態(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為等價狀態(tài)，可合并。2

26、. 已知字母表S = a， b上語言L = w | w中a的個數(shù)是偶數(shù)。（）給出該語言的正規(guī)式（）畫出接收該語言的NFA（）把該NFA轉(zhuǎn)換成等價的DFA（）對該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為：（）對該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如下：（）對該DFA進(jìn)行狀態(tài)

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

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