1、學(xué)習(xí)-好資料計(jì)算理論復(fù)習(xí)題1、設(shè)語言A= w | w含有子串0101,即對(duì)某個(gè)x和y, w=x0101y,字母表為0 , 1a.畫出識(shí)別A的DFA的狀態(tài)圖。b.更多精品文檔2、把下圖的有窮自動(dòng)機(jī)轉(zhuǎn)換成正則表達(dá)式。解：1、加新的開始狀態(tài)和新的結(jié)束狀態(tài)2、刪除狀態(tài)1,通過狀態(tài)1的轉(zhuǎn)換有s一 1 一 2、2一 1 一2*3、刪除狀態(tài)2a b（a ba b）3、設(shè)語言A=www | wC a,b ,利用泵引理證明 A不是正則語言。證明：假設(shè) A是正則的。設(shè)p是泵引理給出的關(guān)于 A的泵長(zhǎng)度。令 S=a ba ba b, S是A的一個(gè)成員且 S的長(zhǎng)度大于p,所以泵引理保證 S可被分成3段S=xyz且 滿足

2、泵引理的3個(gè)條件。根據(jù)條件3, y中只含a,所以xyyz中第一個(gè)a的個(gè)數(shù)將比 后兩個(gè)a的個(gè)數(shù)多，故xyyz不是A2的成員。違反泵引理的條件 1,矛盾。A不是正則的。4、證明在3.1節(jié)開始部分給出的文法G2中，字符串the girl touches the boy with the flower 有兩個(gè)不同的最左派生，敘述這句話的兩個(gè)不同的意思。解：G2如下:（句子一名詞短語動(dòng)詞短語名詞短語一復(fù)合名詞|復(fù)合名詞介詞短語動(dòng)詞短語一復(fù)合動(dòng)詞|復(fù)合動(dòng)詞介詞短語介詞短語一介詞復(fù)合名詞v復(fù)合名詞一 v冠詞 名詞復(fù)合動(dòng)詞一動(dòng)詞|v動(dòng)詞名詞短語冠詞 一 a_|the_ 名詞 一 boy_|girl_|flow

3、er_動(dòng)詞 一 touch_|1ikes_|Sees_介詞 一 with_答：1 .第一種最左派生句子 =名詞短語 動(dòng)詞短語=復(fù)合名詞 動(dòng)詞短語 =冠t名詞 動(dòng)詞短語= a_名詞 動(dòng)詞短語 =a_girl_動(dòng)詞短語 =a_girl_復(fù)合動(dòng)詞 = a_girl_動(dòng)詞 名詞短語 =a_girl_touches_名詞短語 =a_girl_touches_復(fù)合名詞 介詞短語 =a_girl_touches_冠詞 名詞 介詞短語 = a_girl_touches_the_名詞 介詞名詞 =a_girl_touches_the_boy_介詞短語 = a_girl_touches_the_boy_介詞 復(fù)合

4、名詞 =a_girl_touches_the_boy_with_復(fù)合名詞 = a_girl_touches_the_boy_with_冠詞 名詞 =a_girl_touches_the_boy_with_the_名詞 = a_girl_touches_the_boy_with_the_flower含義是：女孩碰這個(gè)帶著花的男孩2 .第二種最左派生句子 =名詞短語 動(dòng)詞短語 復(fù)合名詞 動(dòng)詞短語 =冠，名詞 動(dòng)詞短語= a_名詞動(dòng)詞短語 =a_girl_動(dòng)詞短語 a_girl_復(fù)合動(dòng)詞 介詞短語 = a_girl_動(dòng)詞 名詞短語 介詞短語 a_girl_touches_ 名詞短語 介詞短語 = a

5、_girl_touches_冠詞 名詞 介詞短語 =a_girl_touches_the_ 名詞 介詞短語 = a_girl_touches_the_boy_介詞短語 =a_girl_touches_the_boy_介，復(fù)合名詞 = a_girl_touches_the_boy_with_復(fù)合名詞 =a_girl_touches_the_boy_with_ 冠詞名詞= a_girl_touches_the_boy_with_the_名詞 = a_girl_touches_the_boy_with_the_flower含義是：女孩用花碰這個(gè)男孩5、有自動(dòng)機(jī) M,接受語言L=WcW R | W C

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

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

8、符號(hào)直至結(jié)束。否則拒絕這個(gè)輸入。0,二二0,二8、檢查圖靈機(jī)的形式定義，回答下列問題并解釋你的推理：a.圖靈機(jī)能在它的帶子上寫下空白字符嗎？b.圖靈機(jī)能只包含一個(gè)狀態(tài)嗎？解：a.能。因?yàn)榭瞻追麑儆趲ё帜副恚籅.不能。因?yàn)閝accepfqreject,至少應(yīng)有兩個(gè)狀態(tài)。9、證明正則語言類在并運(yùn)算下封閉。10、設(shè) INFINITE dfa=<A>|A 是一個(gè) DFA ,且 L(A)是一個(gè)無限語言。證明 INFINITE dfa 是 可判定的。證明：設(shè)計(jì)一個(gè)判定 INFINITE dfa的TM M 即可。M= "對(duì)于輸入<A> ,其中A是一個(gè) DFA:1)按照引理2

9、.32證明中的構(gòu)造方法，把 DFA A轉(zhuǎn)換成等價(jià)的正則表達(dá)式。2)掃描正則表達(dá)式，如果包含星號(hào)運(yùn)算符*,則接受；否則拒絕。B是不可數(shù)的。11、設(shè)B是0, 1上所有無限序列的集合，用對(duì)角化方法證明證明：為證明B是不可數(shù)的，必須證明在 B和N之間不存在對(duì)應(yīng)。下面用反證法證之。假 設(shè)在B和N之間存在對(duì)應(yīng)f,現(xiàn)在的任務(wù)是證明它沒有應(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è)無限序列，且此無限序列已與N中的一個(gè)元素配對(duì)。

10、這樣就能保證 x不同于任何已配對(duì)的無限序列。用一個(gè)例子來說明這個(gè)思路。假設(shè)對(duì)應(yīng)f存在，且設(shè)f(1) = 010101，f(2) = 101010，f(3) =等等。則f將1和010101配對(duì)，將2和101010配對(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和H都是一個(gè) CFG,且L(A尸L(B),證明EQcfg是不可判定的。證明：設(shè)TM R判定EQcfg；如下構(gòu)造判定的 ALL cfgTM S :S= "對(duì)于輸入<G>,其中G是CFG;1)在輸入<G, G 1>上運(yùn)行R,其中G1是派生所有可能的串 CFG。2)如果R接受，則接受；如果 R拒絕，則拒絕。”如果R判定EQcfg,則S判定ALL cfg°但由定理6.10, ALL cfg是不可判定的。