形式語言與自動機(jī)理論試題答案解析.doc

《形式語言與自動機(jī)理論試題答案解析.doc》由會員分享，可在線閱讀，更多相關(guān)《形式語言與自動機(jī)理論試題答案解析.doc（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

形式語言與自動機(jī)理論試題答案解析 一、按要求完成下列填空 1. 給出集合{Φ,{Φ}}和集合{ε,0,00}的冪集 （2x4） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 設(shè)∑={0,1},請給出∑上的下列語言的文法 （2x5） (1) 所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既沒有一對連續(xù)的0，也沒有一對連續(xù)的1的串 A→ε|A’|A” A’ →0|01|01A’ A” →1|10|10A” 3. 構(gòu)造識別下列語言的DFA 2x6 (1) {x|x{0，1}+且x以0開頭以1結(jié)尾} （設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€字符為1時，進(jìn)入陷阱狀態(tài)） (2) {x|x{0，1}+且x的第十個字符為1} （設(shè)置一個陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個字符為0，進(jìn)入陷阱狀態(tài)） 二、判斷（正確的寫T，錯誤的寫F） 5x2 1.設(shè)和是集合{a,b,c,d,e}上的二元關(guān)系，則 ( T ) 任取(x.,y),其中x,y，使得。 2.對于任一非空集合A，Φ ( T ) 3.文法G：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型語言2型語言1型語言0型語言 ( F ) 5.s（rs+s）r=rrs（rrs） ( F ) 不成立，假設(shè)r,s分別是表示語言R，S的正則表達(dá)式，例如當(dāng)R={0}，S={1}, L(s(rs+s)*r)是以1開頭的字符串，而L(rr*s(rr*s)*)是以0開頭的字符串.L(s(rs+s)*r) L(rr*s(rr*s)*) 所以s(rs+s)*r rr*s(rr*s)*,結(jié)論不成立 三、設(shè)文法G的產(chǎn)生式集如下，試給出句子aaabbbccc的至少兩個不同的推導(dǎo)（12分）。 bB→bb CB→BC bC→bc cC→cc 推導(dǎo)一： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC =>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc 推導(dǎo)二： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaaBBCCBC =>aaaBBCBCC =>aaabBCBCC =>aaabbCBCC =>aaabbBCCC =>aaabbbCCC =>aaabbbcCC =>aaabbbccC =>aaabbbccc 四、判斷語言{|n>=1}是否為RL，如果是，請構(gòu)造出它的有窮描述(FA,RG或者RL）；如果不是，請證明你的結(jié)論（12分） 解：設(shè)L={|n>=1}。假設(shè)L是RL，則它滿足泵引理。不妨設(shè)N是泵引理所指的僅依賴于 L的正整數(shù)，取Z= 顯然，Z∈L 。 按照泵引理所述，必存在u，v，w。由于|uv|<=N,并且|v|>=1，所以v只可能是由0組成的非空串。不妨設(shè)v=，k>=1 此時有u= ，w= 從而有uvw= 當(dāng)i=2時，有uvw= 又因?yàn)閗>=1, 所以 N+k>N 這就是說不屬于L， 這與泵引理矛盾。所以，L不是RL。 五、構(gòu)造等價于下圖所示DFA的正則表達(dá)式。(12分) S q1 q0 q2 q3 1 0 0 0 1 1 1 0 答案(之一)：( 01+(1+00)((1+00*1)0)*((1+00*1)1) )* (e+(1+00)((1+00*1)0)*00*) q1 q0 q2 q3 1 0 0 0 1 1 1 0 e e X Y e 預(yù)處理： 去掉q3： q1 q0 q2 1 0 1 1+00*1 0 e X Y e 00* 去掉q1： q0 q2 1+00 (1+00*1)0 e X Y e 00* (1+00*1)1 01 q0 e X Y e+(1+00)((1+00*1)0)*00* 01+(1+00)((1+00*1)0)*((1+00*1)1) 去掉q2： 去掉q0： X Y (01+(1+00)((1+00*1)0)*((1+00*1)1))* (e+(1+00)((1+00*1)0)*00*) 六、設(shè)M=（{}，{0,1}，{0,1，B}，{δ}，,B,{}）,其中δ的定義如下： δ（，0）=（，0，R） δ（，1）=（，1，R） δ（，0）=（，0，R） δ（，B）=（，B，R） 請根據(jù)此定義，給出M處理字符串00001000,10000的過程中ID的變化。（10分） 解：處理輸入串00001000的過程中經(jīng)歷的ID變化序列如下： 00001000 00001000 00001000 00001000 000010000 000010000 00001000 00001000 00001000 00001000B 處理輸入串10000的過程中經(jīng)歷的ID變化序列如下： 10000 100000 10000 10000 10000 10000 10000B 七、根據(jù)給定的NFA，構(gòu)造與之等價的DFA。（14分） NFA M的狀態(tài)轉(zhuǎn)移函數(shù)如下表 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(tài) q0 {q0,q1} {q0,q2} {q0,q2} q1 {q3,q0} {q2} q2 {q3,q1} {q2,q1} 終止?fàn)顟B(tài) q3 {q3,q2} {q3 } { q0} 解答： 狀態(tài)說明 狀態(tài) 輸入字符 0 1 2 開始狀態(tài) q0 [q0,q1] [q0,q2] [q0,q2] [q0,q1] [q0,q1,q3] [q0,q2] [q0,q2] [q0,q2] [q0,q1] [q0,q1,q2,q3] [q0,q1,q2] [q0,q1,q2] [q0,q1,q3] [q0,q1,q2,q3] [q0,q1,q2] 終止?fàn)顟B(tài) [q0,q1,q3] [q0,q1,q2,q3] [q0, q2,q3] [q0,q2] 終止?fàn)顟B(tài) [q0,q2,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1, q2] 終止?fàn)顟B(tài) [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1, q2]