形式語言與自動(dòng)機(jī)理論試題(已修改)
2025-08-17 06:26 本頁面
【正文】 形式語言與自動(dò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)造識(shí)別下列語言的DFA 2x6 (1) {x|x206。{0，1}+且x以0開頭以1結(jié)尾} （設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài)） (2) {x|x206。{0，1}+且x的第十個(gè)字符為1} （設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個(gè)字符為0，進(jìn)入陷阱狀態(tài)） 二、判斷（正確的寫T，錯(cuò)誤的寫F） 5x2 {a,b,c,d,e}上的二元關(guān)系，則 ( T ) 任取(x.,y),其中x,y，使得。 ，Φ ( T ) ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) ( T ) （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)*)(s(rs+s)*r) L(rr*s(rr*s)*)所以s(rs+s)*r rr*s(rr*s)*,結(jié)論不成立三、設(shè)文法G的產(chǎn)生式集如下，試給出句子aaabbbccc的至少兩個(gè)不同的推導(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 此時(shí)有u= ，w= 從而有uvw= 當(dāng)i=2時(shí)，有uvw= 又因?yàn)閗=1,所以 N+kN 這就是說不屬于L， 這與泵引理矛盾。所以，L不
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號(hào)-1