1、計(jì)算理論復(fù)習(xí)題1、設(shè)語(yǔ)言A=w | w含有子串0101，即對(duì)某個(gè)x和y，w=x0101y，字母表為0，1a. 畫(huà)出識(shí)別A的DFA的狀態(tài)圖。b. 畫(huà)出識(shí)別A的NFA的狀態(tài)圖（規(guī)定狀態(tài)數(shù)為5）。0,110011010解: a010,1010,1b2、把下圖的有窮自動(dòng)機(jī)轉(zhuǎn)換成正則表達(dá)式。bab12a解:1、加新的開(kāi)始狀態(tài)和新的結(jié)束狀態(tài)bab12asa 2、刪除狀態(tài)1，通過(guò)狀態(tài)1的轉(zhuǎn)換有s12、212a*b2aba*bsa3、刪除狀態(tài)2asa*b(aba*b)*3、設(shè)語(yǔ)言A=www | wa,b*，利用泵引理證明A不是正則語(yǔ)言。證明：假設(shè)A是正則的。設(shè)p是泵引理給出的關(guān)于A的泵長(zhǎng)度。令S=apbapb

2、apb,S是A的一個(gè)成員且S的長(zhǎng)度大于p，所以泵引理保證S可被分成3段S=xyz且滿(mǎn)足泵引理的3個(gè)條件。根據(jù)條件3，y中只含a，所以xyyz中第一個(gè)a的個(gè)數(shù)將比后兩個(gè)a的個(gè)數(shù)多，故xyyz不是A2的成員。違反泵引理的條件1，矛盾。A不是正則的。4、證明在3.1節(jié)開(kāi)始部分給出的文法G2中，字符串the girl touches the boy with the flower 有兩個(gè)不同的最左派生，敘述這句話(huà)的兩個(gè)不同的意思。解: G2如下：句子名詞短語(yǔ)動(dòng)詞短語(yǔ)名詞短語(yǔ)復(fù)合名詞|復(fù)合名詞介詞短語(yǔ)動(dòng)詞短語(yǔ)復(fù)合動(dòng)詞|復(fù)合動(dòng)詞介詞短語(yǔ)介詞短語(yǔ)介詞復(fù)合名詞復(fù)合名詞冠詞名詞復(fù)合動(dòng)詞動(dòng)詞|動(dòng)詞名詞短語(yǔ)冠詞a_

3、|the_名詞boy_|girl_|flower_動(dòng)詞touch_|1ikes_|Sees_介詞with_答：1. 第一種最左派生a_a_girl_a_girl_a_girl_a_girl_touches_ a_girl_touches_a_girl_touches_a_girl_touches_the_a_girl_touches_the_boy_a_girl_touches_the_boy_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_the_a_girl_touche

4、s_the_boy_with_the_flower含義是 ：女孩碰這個(gè)帶著花的男孩2. 第二種最左派生a_a_girl_a_girl_a_girl_a_girl_touches_a_girl_touches_a_girl_touches_the_a_girl_touches_the_boy_a_girl_touches_the_boy_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_a_girl_touches_the_boy_with_the_a_girl_touches_the_boy_with_the_flower含義是：

5、女孩用花碰這個(gè)男孩5、有自動(dòng)機(jī)M，接受語(yǔ)言L(fǎng)=WcW R | Wa,b*c，請(qǐng)給出這臺(tái)PDA的形式定義、狀態(tài)圖，并非形式地描述它的運(yùn)行。6、設(shè)語(yǔ)言A=0n1 n 0n1 n | n0，利用泵引理證明A不是上下文無(wú)關(guān)的。證明：假設(shè)A是上下文無(wú)關(guān)的。設(shè)p是泵引理給出的關(guān)于A的泵長(zhǎng)度。令字符串S=0p1 p 0p1 p,S是A的一個(gè)成員且S的長(zhǎng)度大于p，所以泵引理保證S可被分成5段S=uvxyz且滿(mǎn)足泵引理的3個(gè)條件。 字串vxy一定橫跨S的中點(diǎn)，否則，如果vxy位于S的前一半，把S抽成uv 2 xy 2 z時(shí)，1移到后一半的第一個(gè)位置，因此uv 2 xy 2 z不可能是A的成員。如果vxy位于S的

6、后一半，把S抽成uv 2 xy 2 z時(shí)，0移到后一半的最后一個(gè)位置，因此uv 2 xy 2 z不可能是A的成員。如果字串vxy橫跨S的中點(diǎn)，把S抽成u x y，它形如 0p1 i 0j1 p，其中i和j不可能等于p。于是，S不能被抽取，從而A不是上下文無(wú)關(guān)的。7、設(shè)語(yǔ)言A=w | w至少含有3個(gè)1，字母表為0，1a. 給出產(chǎn)生語(yǔ)言A的上下文無(wú)關(guān)文法。b. 給出產(chǎn)生語(yǔ)言A的下推自動(dòng)機(jī)的非形式描述和狀態(tài)圖。解: a. SA1A1A1AA0A|1A|e讀輸入中的符號(hào)。每讀一個(gè)1，把一個(gè)1推入棧，每讀1個(gè)0，不讀棧也不寫(xiě)棧。同時(shí)非確定性地轉(zhuǎn)移，并把1個(gè)1彈出棧。如果能轉(zhuǎn)移三次，共彈出三個(gè)1，則接受這

7、個(gè)輸入，并繼續(xù)讀輸入符號(hào)直至結(jié)束。否則拒絕這個(gè)輸入。e,1e 1, e10, eee,1e e,1e 1, ee0, ee8、檢查圖靈機(jī)的形式定義，回答下列問(wèn)題并解釋你的推理：a. 圖靈機(jī)能在它的帶子上寫(xiě)下空白字符嗎？b. 圖靈機(jī)能只包含一個(gè)狀態(tài)嗎？解：a. 能。因?yàn)榭瞻追麑儆趲ё帜副鞧；B. 不能。因?yàn)閝acceptqreject，至少應(yīng)有兩個(gè)狀態(tài)。9、證明正則語(yǔ)言類(lèi)在并運(yùn)算下封閉。10、設(shè)INFINITEDFA=|A是一個(gè)DFA，且L(A)是一個(gè)無(wú)限語(yǔ)言。證明INFINITEDFA是可判定的。證明：設(shè)計(jì)一個(gè)判定INFINITEDFA的TM M即可。 M=“對(duì)于輸入，其中A是一個(gè)DFA：1)

8、 按照引理2.32 證明中的構(gòu)造方法，把DFA A轉(zhuǎn)換成等價(jià)的正則表達(dá)式。2) 掃描正則表達(dá)式，如果包含星號(hào)運(yùn)算符*，則接受；否則拒絕。”。11、設(shè)B是0，1上所有無(wú)限序列的集合，用對(duì)角化方法證明B是不可數(shù)的。證明：為證明B是不可數(shù)的，必須證明在B和N之間不存在對(duì)應(yīng)。下面用反證法證之。假設(shè)在B和N之間存在對(duì)應(yīng)f，現(xiàn)在的任務(wù)是證明它沒(méi)有應(yīng)有的性質(zhì)。因?yàn)樗且粋€(gè)對(duì)應(yīng)，必須能將N的所有元素與B的所有元素進(jìn)行配對(duì)。如果能找到B中的一個(gè)x，它和N中的任何元素都不能配對(duì)，則找到了矛盾。為此，實(shí)際構(gòu)造出這樣一個(gè)x。方法如下：在選擇它的每一位數(shù)字時(shí)，都使得：x不同于某個(gè)無(wú)限序列，且此無(wú)限序列已與N中的一個(gè)元素

9、配對(duì)。這樣就能保證x不同于任何已配對(duì)的無(wú)限序列。用一個(gè)例子來(lái)說(shuō)明這個(gè)思路。假設(shè)對(duì)應(yīng)f存在，且設(shè)f(1) = 010101，f(2) = 101010，f(3) =等等。則f將1和010101配對(duì)，將2和101010配對(duì)，依此類(lèi)推。要保證對(duì)每個(gè)n都有x f(n)。為保證x f(1)，只要保證x的第一位數(shù)字不同于f(1) = 010101的第一位數(shù)字，即不是數(shù)字0，令它為1。為保證x f(2)，只要保證x的第二位數(shù)字不同于f(2) = 101010的第一位數(shù)字，即不是數(shù)字0，令它為1。以這種方法繼續(xù)下去，就能夠得到x的所有數(shù)字。不難知道，對(duì)任意n，x都不是f(n)，因?yàn)閤與f(n)在第n位上不同。12、設(shè)EQCFG=|G和H都是一個(gè)CFG，且L(A)= L(B)，證明EQCFG是不可判定的。證明：設(shè)TM R判定EQCFG；如下構(gòu)造判定的ALLCFGTM S： S“對(duì)于輸入，其中G是CFG； 1）在輸入上運(yùn)行R，其中G1是派生所有可能的串CFG。 2）如果R接受，則接受；如果R拒絕，則拒絕?！比绻鸕判定EQCFG，則S判定ALLCFG。但由定理6.1