形式語言與自動(dòng)機(jī)理論試題

1、形式語言與自動(dòng)機(jī)理論試題形式語言與自動(dòng)機(jī)理論試題一、按要求完成下列填空1.給出集合ΦΦ和集合ε000的冪集（2x4）(1)ΦΦΦΦΦ(2)Φε000ε0ε00000ε0002.設(shè)∑=01請(qǐng)給出∑上的下列語言的文法（2x5）(1)所有包含子串01011的串S→X01011YX→ε|0X|1XY→ε|0Y|1Y(2)所有既沒有一對(duì)連續(xù)的0，也沒有一對(duì)連續(xù)的1的串A→ε|A’|A”A’→0|01|01A’A”→1|10|10A”3.構(gòu)造識(shí)別下

2、列語言的DFA2x6(1)x|x?0，1且x以0開頭以1結(jié)尾（設(shè)置陷阱狀態(tài)，當(dāng)?shù)谝粋€(gè)字符為1時(shí)，進(jìn)入陷阱狀態(tài)）1S0110010(2)x|x?0，1且x的第十個(gè)字符為1（設(shè)置一個(gè)陷阱狀態(tài)，一旦發(fā)現(xiàn)x的第十個(gè)字符為0，進(jìn)入陷阱狀態(tài)）1S0101010101100101010101二、判斷（正確的寫T，錯(cuò)誤的寫F）5x21.設(shè)1R和2R是集合abcde上的二元關(guān)系，則3231321)(RRRRRRR???=aaabbbccc推導(dǎo)二：S=aS

3、BC=aaSBCBC=aaaBCBCBC=aaaBBCCBC=aaaBBCBCC=aaabBCBCC=aaabbCBCC=aaabbBCCC=aaabbbCCC=aaabbbcCC=aaabbbccC=aaabbbccc四、判斷語言nnn010|n=1是否為RL，如果是，請(qǐng)構(gòu)造出它的有窮描述(FARG或者RL）；如果不是，請(qǐng)證明你的結(jié)論（12分）解：設(shè)L=nnn010|n=1。假設(shè)L是RL，則它滿足泵引理。不妨設(shè)N是泵引理所指的僅依賴于

4、L的正整數(shù)，取Z=顯然，Z∈L。NNN010按照泵引理所述，必存在u，v，w。由于|uv|=1，所以v只可能是由0組成的非空串。不妨設(shè)v=，k=1此時(shí)有u=，w=從而有uvw=k0jkN??0NNj010i當(dāng)i=2時(shí)，有uvw=又因?yàn)閗=1NNjikjkN010)0(0??2NNkN010?所以NkN這就是說不屬于L，NNkN010?這與泵引理矛盾。所以，L不是RL。五、構(gòu)造等價(jià)于下圖所示DFA的正則表達(dá)式。(12分)答案(之一)：(0