第7講詞法分析測試題

1、1.1.以以n n表示阿拉伯?dāng)?shù)字，描述整數(shù)的正則表示式是（表示阿拉伯?dāng)?shù)字，描述整數(shù)的正則表示式是（ C C）。）。A. nnA. nn* * B.(+|-) nn B.(+|-) nn* * C.(+|-|) nn C.(+|-|) nn* * D. (+|-|)n D. (+|-|)n* * 正確答案：正確答案：C C2.2.用用A A表示（表示（0|1|2|3|4|5|6|7|8|9|a|b|c|e|d|f|A|B|C|D|E|F）, , 用用B B表示表示（0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F）則描述則描述C C語言語言十六進(jìn)制整數(shù)的正則表示式是（十六進(jìn)制整數(shù)的

2、正則表示式是（ C C ）。）。A. (+|-|)(0 x|0X)BBA. (+|-|)(0 x|0X)BB* * B. (+|-|)AAB. (+|-|)AA* * C. (+|-|)(0 x|0X)AAC. (+|-|)(0 x|0X)AA* * D. (0 x|0X)BBD. (0 x|0X)BB* * （C C語言中的語言中的1616進(jìn)制數(shù)必須以進(jìn)制數(shù)必須以 0 x0 x開頭，其中的開頭，其中的x x也不區(qū)分大也不區(qū)分大小寫，字母也不區(qū)分大小寫）小寫，字母也不區(qū)分大小寫）正確答案：正確答案：C C3.詞法分析程序的任務(wù)包括（詞法分析程序的任務(wù)包括（ 1、2、3、4、5 ）。）。按照詞法

3、規(guī)則分割出單詞，識別出其屬性，并以二元式形式輸出按照詞法規(guī)則分割出單詞，識別出其屬性，并以二元式形式輸出刪除程序中的注釋刪除程序中的注釋 刪除程序中的空格刪除程序中的空格發(fā)現(xiàn)程序中的詞法錯誤，并指出位置發(fā)現(xiàn)程序中的詞法錯誤，并指出位置 建立并填寫符號表建立并填寫符號表 正確答案：正確答案： 4.4.是否存在這樣的語言，它們能夠被確定的有限自動是否存在這樣的語言，它們能夠被確定的有限自動機(jī)和正規(guī)文法識別，但是不能用正則表達(dá)式表示。機(jī)和正規(guī)文法識別，但是不能用正則表達(dá)式表示。（B B ）。）。 A.A.存在存在 B.B.不存在不存在 C.C.說不清楚說不清楚 正確答案：正確答案： B B二、判斷題

4、二、判斷題1.1.一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)最多只有一個終態(tài)。（最多只有一個終態(tài)。（ ）2.2.對任何正則表達(dá)式對任何正則表達(dá)式e e都存在一個都存在一個NFA MNFA M，滿足，滿足L(M)=L(e)L(M)=L(e)。（ ）3.3.對任何正則表達(dá)式對任何正則表達(dá)式e e都存在一個都存在一個DFA MDFA M，滿足，滿足L(M)=L(e)L(M)=L(e)。（ ） （至少有一個終態(tài)）（至少有一個終態(tài)）錯錯對對對對start70123456digitdigitdigitdigitdigitdigitother.E+/

5、 Edigitotherother*提示：提示：r+r+等價于等價于rrrr* *；r?r?等價于等價于|r|r三、三、PascalPascal語言無符號數(shù)的正規(guī)定義如下：語言無符號數(shù)的正規(guī)定義如下：numdigit+numdigit+（.digit+.digit+）?(E(+|-)?digit+)?(E(+|-)?digit+)?其中，其中，digitdigit表示數(shù)字，用狀態(tài)轉(zhuǎn)換圖表示接受無符號數(shù)的表示數(shù)字，用狀態(tài)轉(zhuǎn)換圖表示接受無符號數(shù)的NFANFA四、構(gòu)造正規(guī)式（四、構(gòu)造正規(guī)式（0|10|1）* *| |（1111）* *的的DFADFA314start 201 894657 11112

6、131 1 0 10 輸入符號輸入符號01狀態(tài)狀態(tài) T0= -closure(0) =0,1,2,3,4,5,9,10,11,14 T0未被標(biāo)記，且為終結(jié)狀態(tài)未被標(biāo)記，且為終結(jié)狀態(tài) T0T0 =0, 1, 2,3, 4,5, 9,10, 11,14 T1= -closure(move(T0,0) = -closure(6) =1,2,3,4,5, 6,8, 9,10,11,14 T1未被標(biāo)記，且為終結(jié)狀態(tài)未被標(biāo)記，且為終結(jié)狀態(tài)輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1T0 =0,1,2,3,4,5,9,10,11,14T1 =1,2,3,4,5, 6,8, 9,10,11,14 T2= -

7、closure(move(T0,1) = -closure(7,12) =1,2,3, 4,5, 7,8, 9,10, 11,12, 14 T2未被標(biāo)記，且為終結(jié)狀態(tài)未被標(biāo)記，且為終結(jié)狀態(tài)輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1 T2 T2T0 =0,1,2,3,4,5,9,10,11,14T1 =1,2,3,4,5,6,8,9,10,11,14T2 =1,2,3,4,5,7,8,9,10,11,12,14T3= -closure(move(T1,0) = -closure(6) =1,2,3,4,5, 6,8, 9,10,11,14輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1 T2

8、T2 T3= T1已被標(biāo)記已被標(biāo)記 T1T0 =0,1,2,3,4,5,9,10,11,14T1 =1,2,3,4,5,6,8,9,10,11,14T2 =1,2,3,4,5,7,8,9,10,11,12,14 T3= -closure(move(T1,1) = -closure(7,12) =1,2,3,4,5,7,8,9,10,11,12,14輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T1 T2 T3= T2已被標(biāo)記已被標(biāo)記T0 =0,1,2,3,4,5,9,10,11,14T1 =1,2,3,4,5,6,8,9,10,11,14T2 =1,2,3,4,5,7,8,9,1

9、0,11,12,14 T3= -closure(move(T2,0) = -closure(6) =1,2,3,4,5, 6,8, 9,10,11,14輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T3= T1已被標(biāo)記已被標(biāo)記 T1 T1 T2T0 =0,1,2,3,4,5,9,10,11,14T1 =1,2,3,4,5,6,8,9,10,11,14T2 =1,2,3,4,5,7,8,9,10,11,12,14 T3= -closure(move(T2,1) = -closure(7,12,13) =1,2,3,4,5,7,8,9,10,11,12,13,14輸入符號輸入符號01

10、狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T3未被標(biāo)記，且為終結(jié)狀態(tài)未被標(biāo)記，且為終結(jié)狀態(tài) T1 T1 T2 T3 T3T0 =0,1,2,3,4,5,9,10,11,14T1 =1,2,3,4,5,6,8,9,10,11,14T2 =1,2,3,4,5,7,8,9,10,11,12,14 T3=1,2,3,4,5,7,8,9,10,11,12,13,14T4= -closure(move(T3,0) = -closure(6) 輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T1 T1 T2 T3 T3 T4= T1已被標(biāo)記已被標(biāo)記 T1T0 =0,1,2,3,4,5,9,10,1

11、1,14T1 =1,2,3,4,5,6,8,9,10,11,14T2 =1,2,3,4,5,7,8,9,10,11,12,14 T3=1,2,3,4,5,7,8,9,10,11,12,13,14T4= -closure(move(T3,1) = -closure(7,12,13) 輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T1 T1 T2 T3 T3 T4= T3已被標(biāo)記已被標(biāo)記 T1 T3start03210101輸入符號輸入符號01狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T1 T1 T2 T3 T3 T1 T30101T0 =0,1,2,3,4,5,9,10,11,14T

12、1 =1,2,3,4,5,6,8,9,10,11,14T2 =1,2,3,4,5,7,8,9,10,11,12,14 T3=1,2,3,4,5,7,8,9,10,11,12,13,14 五、設(shè)五、設(shè)M=(x,y,(a,b),f,x,y)M=(x,y,(a,b),f,x,y)為一個非確定的有限為一個非確定的有限自動機(jī)，其中自動機(jī)，其中f f定義為：定義為：f(x,a)=x,yf(x,a)=x,y，f(x,b)=yf(x,b)=y，f(y,b)=x,yf(y,b)=x,y，請構(gòu)造相應(yīng)的確定的有限自動機(jī)。，請構(gòu)造相應(yīng)的確定的有限自動機(jī)。yxstartaabbb輸入符號輸入符號ab狀態(tài)狀態(tài) T0yxs

13、tartaabbbT0= -closure(x) =x T0未被標(biāo)記未被標(biāo)記輸入符號輸入符號ab狀態(tài)狀態(tài) T0yxstartaabbbT0=xT1= -closure (move(T0,a) = -closure(x,y) =x,y T1未被標(biāo)記，且為終結(jié)狀態(tài)未被標(biāo)記，且為終結(jié)狀態(tài) T1 T1輸入符號輸入符號ab狀態(tài)狀態(tài) T0yxstartaabbbT0=xT1=x，yT2= -closure (move(T0,b) = -closure(y) =y T2未被標(biāo)記，且為終結(jié)狀態(tài)未被標(biāo)記，且為終結(jié)狀態(tài) T1 T2 T1 T2輸入符號輸入符號ab狀態(tài)狀態(tài) T0yxstartaabbbT0=xT1=

14、x，yT2=yT3= -closure (move(T1,a) = -closure(x，y) =x，y T1 T2 T1 T2 T3= T1已被標(biāo)記已被標(biāo)記 T1輸入符號輸入符號ab狀態(tài)狀態(tài) T0yxstartaabbbT0=xT1=x，yT2=yT3= -closure (move(T1,b) = -closure(x,y) =x,y T1 T2 T1 T2 T3= T1已被標(biāo)記已被標(biāo)記 T1 T1輸入符號輸入符號ab狀態(tài)狀態(tài) T0yxstartaabbbT0=xT1=x，yT2=yT3= -closure (move(T2,a) = -closure( ) = T1 T2 T1 T2 T

15、1 T1 輸入符號輸入符號ab狀態(tài)狀態(tài) T0yxstartaabbbT0=xT1=x，yT2=yT3= -closure (move(T2,b) = -closure(x,y) =x,y T1 T2 T1 T2 T1 T1 T3= T1已被標(biāo)記已被標(biāo)記 T1輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T2 T1 T2 T1 T1 T120starta1ba，bbT0=xT1=x，yT2=y 六、請寫出在字母表六、請寫出在字母表=a=a，bb上，不是上，不是a a開頭的，以開頭的，以aaaa結(jié)尾結(jié)尾的字符串集合的正則表達(dá)式，并構(gòu)造與之等價狀態(tài)最少的的字符串集合的正則表達(dá)式，并構(gòu)造與之等價狀態(tài)最少的

16、DFADFA。 正規(guī)表達(dá)式為：正規(guī)表達(dá)式為：b b（a|ba|b）* *aaaab0start2 1ab 73546 10aa98 T0= -closure(0) =0 T0未被標(biāo)記未被標(biāo)記輸入符號輸入符號ab狀態(tài)狀態(tài) T0T0= 0T1= -closure (move(T0,a) = 輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T0= 0T1= -closure (move(T0,b) = -closure(1) =1,2,3,4,8輸入符號輸入符號ab狀態(tài)狀態(tài) T0T1未被標(biāo)記未被標(biāo)記 T1 T1 T0= 0T1=1,2,3,4,8T2= -closure (move(T1,a) = -closu

17、re(5,9) =2,3,4,5,7,8,9輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T1 T2T2未被標(biāo)記未被標(biāo)記 T2T0= 0T1=1,2,3,4,8 T2= 2,3,4,5,7,8,9T3= -closure (move(T1,b) = -closure(6) =2,3,4,6,7,8 輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T1 T2T3未被標(biāo)記未被標(biāo)記 T2 T3 T3T0= 0T1=1,2,3,4,8 T2= 2,3,4,5,7,8,9T3=2,3,4,6,7,8 T4= -closure (move(T2,a) = -closure(5,9,10) =2,3,4,5,7,8,

18、9,10輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T1 T2T4未被標(biāo)記未被標(biāo)記 T2 T3 T3 T4 T4T0= 0T1=1,2,3,4,8 T2= 2,3,4,5,7,8,9T3=2,3,4,6,7,8 T4=2,3,4,5,7,8,9,10T5= -closure (move(T2,b) = -closure(6) =2,3,4,6,7,8輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T3 T3 T4 T4 T5= T3已被標(biāo)記已被標(biāo)記 T3T0= 0T1=1,2,3,4,8 T2= 2,3,4,5,7,8,9T3=2,3,4,6,7,8 T4=2,3,4,5,7,8,9

19、,10T5= -closure (move(T3,a) = -closure(5,9) =2,3,4,5,7,8,9輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T3 T3 T4 T4 T5= T2已被標(biāo)記已被標(biāo)記 T3 T2T0= 0T1=1,2,3,4,8 T2= 2,3,4,5,7,8,9T3=2,3,4,6,7,8 T4=2,3,4,5,7,8,9,10T5= -closure (move(T3,b) = -closure(6) =2,3,4,6,7,8輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T3 T3 T4 T4 T5= T3已被標(biāo)記已被標(biāo)記 T3 T2 T3T0= 0T1=1,2,3,4,8 T2= 2,3,4,5,7,8,9T3=2,3,4,6,7,8 T4=2,3,4,5,7,8,9,10T5= -closure (move(T4,a) = -closure(5,9,10) =2,3,4,5,7,8,9,10輸入符號輸入符號ab狀態(tài)狀態(tài) T0 T1 T1 T2 T2 T3 T