第二、三章習(xí)題講

1、2008-10-282.1 考慮下面的上下文無關(guān)文法：S SS+ | SS* |a試說明如何使用該文法生成串a(chǎn)a+a*。試為aa+a*構(gòu)造一個(gè)分析樹。該文法產(chǎn)生的語言是什么？ANSWER:S SS* SS+S* aa+a*圖以a為變量，+和*為二元操作符的后綴表達(dá)式22.2 下面的文法產(chǎn)生什么語言？S0S1|010n1n（n=1,2,） S+SS|-SS|a以a為變量，+和-為二元操作符的前綴表達(dá)式SS(S)S|括號的匹配SaSbS|bSaS| 由相同數(shù)目的a、b組成的字符串，或者空串。3Sa|S+S|SS|S*|(S)以a為數(shù)據(jù)元素，具有合并、連接、閉包和括號操作符的表達(dá)式。a是表達(dá)式，若S

2、是表達(dá)式則S+S（表達(dá)式的合并）、SS（表達(dá)式的串聯(lián)）、S*（表達(dá)式的閉包運(yùn)算）都是表達(dá)式。4注意事項(xiàng)不是終結(jié)符，應(yīng)該省略。但是如果包含空串，則需特別強(qiáng)調(diào)。產(chǎn)生式可以交替使用描述生成何種語言時(shí)，應(yīng)當(dāng)描述完整的字母表52.3 練習(xí)2.2中哪些文法具有二義性？c、d、e具有二義性?？赏ㄟ^畫某個(gè)串的分析樹來說明67 S aSbS | bSaS |a) 試說明此文法是二義性的. 可以從句子abab有兩個(gè)不同的最左推導(dǎo)來說明. S aSbS abS abaSbS ababS abab lm lm lm lm lm S aSbS abSaSbS abaSbS ababS abab lm lm lm lm

3、lm 句子abab有兩個(gè)不同的最左推導(dǎo), 該句子是二義性的 . 所以此文法是二義性的.8(b) 對于句子abab構(gòu)造兩個(gè)相應(yīng)的最右推導(dǎo). S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab abab rm rm rm rm rm (c)對于句子abab構(gòu)造兩個(gè)相應(yīng)的分析樹.判斷一個(gè)文法是否具有二義性，可以通過判斷是否存在一個(gè)具有多棵分析樹的記號串。3.3 識別下面的各段程序中構(gòu)成記號的詞素，并給出每個(gè)記號的合理屬性值： 程序：int max（i，j）int i，j；/*返回整數(shù)i和j的最大者*/retu

4、rn ij? i:j；9詞素記號屬性intintmaxid指向符號表max條目的指針(標(biāo)點(diǎn)符號左括號iid指向符號表i條目的指針,標(biāo)點(diǎn)符號逗號jid指向符號表j條目的指針)標(biāo)點(diǎn)符號右括號;標(biāo)點(diǎn)符號分號returnreturn操作符大于號?操作符問號:操作符冒號標(biāo)點(diǎn)符號右大括號標(biāo)點(diǎn)符號左大括號10注意事項(xiàng)記號token（終結(jié)符），模式pattern，詞素lexeme（源程序的字符序列）可構(gòu)成token（記號）的：關(guān)鍵字，操作符，標(biāo)識符，常量，字符串，標(biāo)點(diǎn)符號每個(gè)詞素都要一一記錄注釋是在詞法分析時(shí)忽略的，而詞法分析器對程序采取非常局部的觀點(diǎn)。 不是每個(gè)token都要有屬性1112(a) 0 ( 0

5、 | 1)* 0(b) ( ( | 0 ) 1* ) *由0和1組成且以0開始和結(jié)束的符號串全體.(c) ( 0 | 1 )* 0 ( 0 | 1) ( 0 | 1)由0和1組成的符號串全體.由0和1組成且以000,001,010或011結(jié)束的符號串全體.長度大于等于3且倒數(shù)第3個(gè)字符為0的01符號串全體.3.6 試描述下列正規(guī)表達(dá)式所表示的語言:13(d) 0*10*10*10*(e) ( 00 | 11)* ( ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )*有且只有3個(gè)1的0、1字符串全體.帶有偶數(shù)個(gè)0和偶數(shù)個(gè)1的由0和1組成的符號串全

6、體.帶有偶數(shù)個(gè)a和偶數(shù)個(gè)b的符號串全體.( (aa|bb) | (ab|ba) (aa|bb)* (ab|ba) )*注意事項(xiàng)在描述語言的時(shí)候應(yīng)該準(zhǔn)確，精簡。語言給定字母表上任意一個(gè)字符串集合。句子（字）屬于語言的字符串，字母表中符號的有窮序列?？兆址涂占?43.7 試寫出下列語言的正規(guī)定義：a）包含5個(gè)元音的所有字母串，其中元音按順序出現(xiàn)。X=輔音字母全體(X|(A|a)*(A|a)(X|(E|e)*(E|e)(X|(I|i)*(I|i)(X|(O|o)*(O|o)(X|(U|u)*(U|u)X*15保證元音字母至少出現(xiàn)一次b) 按詞典遞增序排列的所有字母串。( a | A)* ( b

7、| B)* ( c | C)*.( z | Z)*1617 d)沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串全體. e) 最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號串全體令 ri = i | , i=0,1,2,.,9 R0|R1|R2|.|R9記為 Ri i(0,1,2.,9)P(0,1,2.,9)表示0,1,2.,9的全排列 ri0ri1.ri9 i0i1. i9P(0,1,2.,9) i ri0ri1.ri9i(0,1,2.,9) i0i1. i9P(0,1,2.,9)18 f) 帶有偶數(shù)個(gè)0和奇數(shù)個(gè)1的由0和1組成的符號串全體. E為帶有偶數(shù)個(gè)0和1的由0和1組成的符號串全體.即 ( 00 | 11)* (

8、 ( 01 | 10 ) ( 00 | 11)* ( 01 | 10 ) ( 00 | 11)* )* E 1 E | E 0 E 1 E 0 E h) 不包含子串011的由0和1組成的符號串全體. i) 不包含子序列011的由0和1組成的符號串全體1*0* (10* |) 1*( 0 | (01) )*19 h) 不包含子串011的由0和1組成的符號串全體. i) 不包含子序列011的由0和1組成的符號串全體1*( 0 | (01) )*1*0* (10* |) (00 | 11) ( (01 | 10) (00 | 11) (01 | 10) (00 | 11) ) 所有由偶數(shù)個(gè)0和偶數(shù)個(gè)

9、1構(gòu)成的串。另外，和該正規(guī)式等價(jià)的正規(guī)式有( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 。更簡單的描述( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 它是基于這樣的考慮，滿足要求的最簡單的串有三種形式（空串除外）：1002113(01 | 10) (00 | 11) (01 | 10)它們?nèi)我舛啻蔚闹貜?fù)構(gòu)成的串仍然滿足要求。20寫出語言“由偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的所有0和1的串”的正規(guī)定義。even_0_even_1 (00 | 11) ( (01 | 10) (00 | 11) (01 | 10

10、) (00 | 11) ) even_0_odd_1 1 even_0_even_1 |0 (00 | 11) (01 | 10) even_0_even_1對于偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的串，其第一個(gè)字符可能是0或1。如果是1，那么剩下的部分一定是偶數(shù)個(gè)0和偶數(shù)個(gè)1。如果是0，那么經(jīng)過若干個(gè)00或11，一定會出現(xiàn)一個(gè)01或10，才能保證0的個(gè)數(shù)是偶數(shù)，1的個(gè)數(shù)是奇數(shù)。若串還沒有結(jié)束，剩余部分一定是偶數(shù)個(gè)0和偶數(shù)個(gè)1。21注意事項(xiàng)正規(guī)定義：為了讓正規(guī)表達(dá)式的表示簡潔，可以對正規(guī)式命名。 d1 r1 d2 r2 . . . dn rn各個(gè)di的名字都不同每個(gè)ri都是d1, d2, , di-1 上的

11、正規(guī)式 應(yīng)該寫出正規(guī)定義或者正則表達(dá)式，狀態(tài)圖必須化簡223.16 用算法用算法3.3 構(gòu)造非確定有窮自動機(jī)，給出構(gòu)造非確定有窮自動機(jī)，給出處理輸入串處理輸入串a(chǎn)babbab的狀態(tài)轉(zhuǎn)換序列：的狀態(tài)轉(zhuǎn)換序列：23ababbab的狀態(tài)轉(zhuǎn)換序列24c) (|a)b*)*25ababbab的狀態(tài)轉(zhuǎn)換序列263.17 用算法3.2把練習(xí)3.16中的NFA轉(zhuǎn)換成DFA。給出它們處理串a(chǎn)babbab的狀態(tài)轉(zhuǎn)換序列。(a|b)*-closure(0) = 0,1,2,4,7 = A-closure(move(A,a) = -closure(3) = 1,2,3,4,6,7 = B-closure(move(A

12、,b) = -closure(5) =1,2,4,5,6,7 = C-closure(move(B,a) = -closure(3) = 1,2,3,4,6,7-closure(move(B,b) = -closure(5) = 1,2,4,5,6,72728-closure(move(C,a) = -closure(3) = 1,2,3,4,6,7-closure(move(C,b) = -closure(5) = 1,2,4,5,6,7 則DFA為：3.17 用算法3.2把練習(xí)3.16中的NFA轉(zhuǎn)換成DFA。給出它們處理串a(chǎn)babbab的狀態(tài)轉(zhuǎn)換序列。-closure(0) = 0,1,2

13、,3,4,6,7,8,10,11=A-closure(move(A,a) = -closure(5) = 1,2,3,4,5,6,7,8,10,11=B-closure(move(A,b) = -closure(9) =1,2,3,4,6,7,8,9,10,11=C29c) ( |a)b*)*-closure(move(B,a) = -closure(5) = 1,2,3,4,5,6,7,8,10,11=B-closure(move(B,b) = -closure(9) = 1,2,3,4,5,6,7,8,10,11=C-closure(move(C,a) = -closure(5) = 1,

14、2,3,4,5,6,7,8,10,11=B-closure(move(C,b) = -closure(9)= 1,2,3,4,5,6,7,8,10,11=C則DFA為：30畫狀態(tài)圖注意事項(xiàng)應(yīng)明確地指出開始狀態(tài)應(yīng)明確地指出終止?fàn)顟B(tài)，不一定只有一個(gè)NFA轉(zhuǎn)化為DFA時(shí)，NFA的狀態(tài)集合包含有接受狀態(tài)，那么對應(yīng)的DFA狀態(tài)也是接受狀態(tài) 313.22 如果兩個(gè)正規(guī)表達(dá)式的最少狀態(tài)如果兩個(gè)正規(guī)表達(dá)式的最少狀態(tài)DFA除狀態(tài)名以外完除狀態(tài)名以外完全相同，則這兩個(gè)正規(guī)表達(dá)式等價(jià)。全相同，則這兩個(gè)正規(guī)表達(dá)式等價(jià)。(a*|b*)*A: -closure(0) = 0,1,2,3,5,6,7,9,10,11,B:

15、-closure(move(A,a) = -closure(4) = 1,2,3,4,5,6,7,9,10,11C: -closure(move(A,b) = 1,2,3, 6,7,8,9,10,113233A狀態(tài)狀態(tài)abABCBBCCBC注意事項(xiàng)該題為證明題，做題思路為構(gòu)造各個(gè)正規(guī)表達(dá)式的最小狀態(tài)DFA。應(yīng)該有中間步驟。a)和c)可以見3.17中的解答。343.23 對于下列正規(guī)表達(dá)式構(gòu)造最小狀態(tài)的DFA.解題步驟：1，從正則表達(dá)式到NFA2，從NFA到DFA（子集構(gòu)造法）3，最小化DFA（算法3.6）353.23 對于下列正規(guī)表達(dá)式構(gòu)造最小狀態(tài)的DFA.a) (a|b)*a(a|b)36(

16、b) (a|b)*a(a|b)(a|b) 解法一37AstartBabHGaCDaaaEFabaaabbbb最小化DFAa1start2a43babNFAbab) (a | b) a (a | b) (a | b) 解法二3820134567aabbaabbstartbaababab圖圖1.11 接收接收(a | b) a (a | b) (a | b)的的DFA20134567aaba,baabbstart圖圖1.12 構(gòu)造過程的第一步構(gòu)造過程的第一步c) (a | b) a (a | b) (a | b) (a | b)一共有16個(gè)狀態(tài)，滿足定理3.23 d）正規(guī)表達(dá)式(a | b) a

17、(a | b) (a | b) (a | b)共有n-1個(gè)(a | b)，對應(yīng)的任何一個(gè)DFA至少有2n個(gè)狀態(tài)。證明方法如前圖方法所示。39400142233567119101213813141517182119202216startabaaaabbb圖：帶圖：帶轉(zhuǎn)移的轉(zhuǎn)移的NFA第一步：第二步A= -closure(0) B= -closure(3,8) C= -closure(5) D= -closure(3,8,10) E= -closure(5,12) F= -closure(3,8,10,15) G= -closure(5,12,17) H= -closure(3,8,15) I=

18、-closure(5,17) J= -closure(3,8,10,15,20) K= -closure(5,12,17,22) 41L= -closure(3,8,15,20) M= -closure(5,17,22) N= -closure(3,8,10,20) O= -closure(5,12,22) P= -closure(3,8,20) Q= -closure(5,22) 狀態(tài)狀態(tài)abABCBDECBCDFGEHIFJKGLMHNOIPQJIKKLMLNOMPQNFGOHIPDEQBC42狀態(tài)轉(zhuǎn)移表：狀態(tài)轉(zhuǎn)移表：第三步：應(yīng)用算法3.6消除狀態(tài)C之后得到的最少狀態(tài)DFA：給出奇數(shù)個(gè)0奇數(shù)個(gè)1的正規(guī)表達(dá)式44012311110000start接受奇數(shù)個(gè)接受奇數(shù)個(gè)0和奇數(shù)個(gè)和奇數(shù)個(gè)1的的的的DFA偶0偶1偶0