浙江大學計算機考博試題計算理論及答案

1、計算理論字母表： 一個有窮的符號集合。字母表上的 字符串 是該字母表中的符號的有窮序列。一個字符串的 長度 是它作為序列的長度。連接 反轉(zhuǎn) Kleene 星號 L* ， 連接 L 中 o 個或多個字符串得 到的所有字符串的集合。有窮自動機： 描述能力和資源極其有限的計算機模型。有窮自動機是一個5 元組 M=(K , 刀,、 ,s,F ), 其中1) K是一個有窮的集合，稱為狀態(tài)集2) 刀是一個有窮的集合，稱為字母表3) 是從KXSA K的函數(shù)，稱為轉(zhuǎn)移函數(shù)4) s ? K 是初始狀態(tài)5) F K 是接收狀態(tài)集M 接收的語言是 M 接收的所有字符串的集合，記作 L(M).對于每一臺非確定型有窮自

2、動機，有一臺等價的確定型有窮自動機有窮自動機接受的語言在并、連接、 Kleene 星號、補、交運算下 是封閉的。每一臺非確定型有窮自動機都等價于某一臺確定型有窮自動機。一個語言是正則的當且僅當它被有窮自動機接受。正則表達式：稱 R 是一個正則表達式，如果 R 是1) a,這里a是字母表刀中的一個元素。2) 只包含一個字符串空串的語言3),不包含任何字符串的語言4) (R1 u R2),這里R1和R2是正則表達式5) (R10R2),這里R1和R2是正則表達式6) (R1*),這里R1*是正則表達式一個語言是正則的當且僅當可以用正則表達式描述2000年4月1根據(jù)圖靈機理論，說明現(xiàn)代計算機系統(tǒng)的理

3、論基礎(chǔ)1936年，圖靈向倫敦權(quán)威的數(shù)學雜志投了一篇論文，題為論數(shù)字計算在決斷難題中的應用。在這篇開創(chuàng)性的論文中，圖靈給可計算性”下了一個嚴格的數(shù)學定義，弁提出著名的圖靈機”(Turing Machine)的設(shè)想。圖靈機”不是一種具體的機器，而是一種思想模型，可制造一種十分簡單但運算能力極強的計算機裝置，用來計算所有能想像得到的可計算函數(shù)。這個裝置由下面幾個部分組成：一個無限長的紙帶，一個讀寫頭。(中間那個大盒子)，內(nèi)部狀態(tài)(盒子上的方塊，比如A,B,E,H ),另外，還有一個程序?qū)@個盒子進行控制。這個裝置就是根據(jù)程序的命令以及它的內(nèi)部狀態(tài)進行磁帶的讀寫、移動。工作帶被劃分為大小相同的方格，每

4、一格上可書寫一個給定字母表上的符號?？刂破骺梢栽趲献笥乙苿?它帶有一個讀寫出一個你期待的結(jié)果。這一理論奠定了整個現(xiàn)代計算機的理論基礎(chǔ)。圖靈機”更在電腦史上與馮諾依曼機”齊名，被永遠載入計算機的發(fā)展史中。圖靈機在理論上能模擬現(xiàn)代數(shù)字計算機的一切 運算，可視為現(xiàn)代數(shù)字計算機的數(shù)學模型。實際上一切"可計算"函數(shù)都等價于圖靈機可計算函數(shù)，而圖靈機可計算函數(shù)類又等價于一般遞歸函數(shù)類。2、說明按喬姆斯基分類，語言、文法、自動機的關(guān)系喬姆斯基將語言定義為，按一定規(guī)律構(gòu)成的句子或符號串string的有限的或無限的集合，記為Lo數(shù)目有限的規(guī)則叫文法，記為Go刻畫某類語言的有效手段是文法和自

5、動機。文法與自動機的關(guān)系：形式文法是從生成的角度來描述語言的，而自動機是從識別的角度來描述語言的.文法和自動機是形式語言理論的基本內(nèi)容。對某種語言來說，如果存在一個該語言的生成過程，就一定存在一個對于它的識別過程.就描述語言來講，形式語言和自動機是統(tǒng)的.文法在形式上定義為四元組：G= （ VN,VT,S,P ） ,VN是非終極符號，VT是終極符號，S是VN中的初始符號，P是重寫規(guī)則形式語百自動機（接收機）非限定性語言圖靈機上下文有關(guān)語言線性有界自動機上下文無關(guān)語言下推式存貯自動機有限自動機圖1*1形式語害和自動機的關(guān)聯(lián)歸類圖文法是定義語言的一個數(shù)學模型，而自動機可看作是語言的識別系統(tǒng)對于一個文

6、法產(chǎn)生的語言，可以構(gòu)造相應自動機接受該語言：一個自動機接受的語言，可以構(gòu)造對應的文法產(chǎn)生該語言。一定類型的自動機和某種類型的文法具有等價性O(shè)2、喬姆斯基根據(jù)轉(zhuǎn)換規(guī)則將文法分作4類。每類文法的生成能力與相應的語言自動機（識別語言的裝置）的識別能力等價，即 4 類文法分別與 4 種語言自動機對應文法自動機0型無限制文法圖靈機1型上下文有美文法線性有界自動機2型上下文無關(guān)文法r后進先出自動機3型有限狀態(tài)的正則文法有限自動機最常見文法的分類系統(tǒng)是諾姆喬姆斯基于1956年發(fā)展的喬姆斯基譜系，這個分類譜系把所有的文法分成四類型：無限制文法、上下文相關(guān)文法、上下文無關(guān)文法和正規(guī)文法。四類文法對應的語言類分別

7、是遞歸可枚舉語言、上下文相關(guān)語言、上下文無關(guān)語言和正規(guī)語言。這四種文法類型依次擁有越來越嚴的產(chǎn)生式規(guī)則，同時文法所能表達的言也越來越少。盡管表達能力比無限文法和上下文相關(guān)文法要弱，但由于高效率的實現(xiàn)，四類文法中最重要的上下文無關(guān)文法和正規(guī)文法。例如對下文無關(guān)語言存在算法可以生成高效的LL分析器和LR分析器3、證明HALT(X R,X)不是可計算的4、(1)、證明遞歸集都是遞歸可枚舉集。(2)、舉例屬于遞歸可枚舉集但不是遞歸集的集合，并證明之。5、(1)、證明L = (a,b)*|a,b的個數(shù)相同為上下文無關(guān)語言。(2)、并證明其不是正則的。P56假設(shè)L是正則的，則根據(jù)在交下的封閉性，L n a

8、*b*也是封閉的，而后者正好是 L1= a ibi:i仝0,假設(shè)L1是正則的，則存在滿足泵引理的整數(shù)no考慮字符串w= anbn? Lo根據(jù)定理可 以寫成w=xyz使得|xy| w n,且滬e,即y=ai,其中i > 0.但是xz= aA"b" L,與定理矛盾。2000年10月1、(1) 給出圖靈機的格局、計算及圖靈機口計算函數(shù)f的精確定義。(2 )對圖靈機模型而言，church論題是什么？(3 )當x是完全平方時值為 3x,否則為3x+1證明其是原始遞歸函數(shù)。心)二嚴if)=*12x +1 else設(shè)嘴心O時LGO艇工的所白因子上利：cr(O)=0.試證切bCO足飾

9、始遞！ Hrmwlieie.J 1, if k工 | ,Vj jo*, else 區(qū)(巧.”2)3、設(shè)7T(X)足小r等兀的墨數(shù)的個數(shù).試證明更是原始遞H的兀(工)二工gd)r-01, if xa<X2 & pnme(xY) (k else2 、證明0( X, X) 是不可計算的。3、證明L=ambn|m,n>O,m 豐n是上下文無關(guān)的，但不是正則的利用上下文無關(guān)語言在并、連接、 Kleene 星號下是封閉的。正則語言在交運算下封閉。4、A為有窮字母表，L是A*的無窮子集，( 1 ) 證明存在無窮序列 3 0, 3 1, 3 2；它由L 的所有字組成，每個字恰好在其中只出現(xiàn)

10、一次。(2) 是否存在從L 構(gòu)造序列 3 0, 3 1, 3 2?的算法( 即 i 由計算 3 i , 為什么？2001 年 4 月1 、 ( 1) 當 x 是完全平方時值為2x ，否則為2x+1 證明其是原始遞歸函數(shù)。(3) 對圖靈機模型而言， church 論題是什么？(4) 通用圖靈機的描述。2、 ( 1)用有窮自動機構(gòu)造正則語言，以 a2b 結(jié)尾的字符串組成的正則語言 L( 2) L=a3n bn |n>0 為上下文無關(guān)， 但不是正則。3、A為字母表，L為A*上任意的語言。闡述其喬姆斯基層次及用可計算性表述它們的關(guān)系。4、證明不存在可計算函數(shù)h(x),使0 (x,x)盹h(x,x

11、)= 0 (x,x)+a,a N, 0 (x,y)是編號為y輸入 為x時的程序。2001 年 10 月1 、 a, b 上遞歸枚舉語言是否可數(shù)？證明2 、 L=a , b, c 數(shù)目相同的語言 是否 CFL （上下文無關(guān)）？證明 p95證：不是上下文無關(guān)的。假設(shè)L 是上下文無關(guān)的，則它與正則語言a*b*C*的交也是上下文無關(guān)的。令L1= anbncn:n±0假設(shè) L1 是上下文無關(guān)語言。取常數(shù) p, 3 = ap bp cp , I 3 I = 3p > p將3寫成=uvxyz使得v或y不是空串且uvxy'zeLiI=0,1,2 其中 I xy l> 1 且 I

12、xuy l< p.有兩種可能他們都導致矛盾。如果 vy 中 a 、 b 、 c 三個符號都出現(xiàn)，則 v 和 y 中必有一個至少含有 abc 中的兩個符號。于是uv2xy2z 中 abc 的排列順序不對，有的 b 在 a 前或 c 在 a 或 b 前。如果 vy 中只出現(xiàn) a、 b、 c 中的一個或兩個符號，貝 Uuv2xy2z中 a 、 b 、 c 的個數(shù)不相等。?與L1 是上下文無關(guān)語言假設(shè)矛盾。綜上， L 不是 2 型語言。3 、 被 2, 3 整除的非負整數(shù)的十進制表示的集合是否正則。刀=1 , 2 ,9 , L刀*,令L1是非負整數(shù)十進制表示的集合，容易看到L1=0 U 1 ,

13、2 ,9刀*,由于L1是用正則表達式表示的，故它是一個正則語言。令 L2 是可以被 2 整除的非負整數(shù)的十進制表示的集合。 L2 正好是以 0, 2 , 4 , 6 , 8結(jié)尾的 L1 的成員組成的集合，即 L2=L 1 PE *0 , 2 , 4 , 6 , 8 ，根據(jù)正則語言在交運算下封閉原則，故L2 也是一個正則語言。令是可以被3 整除的非負整數(shù)的十進制表示的集合?一個數(shù)可以被3 整除當且僅當它的數(shù)字之和可以被3 整除。構(gòu)造一臺有窮自動機，用它的有窮控制器保存輸入數(shù)字的模3 和。 L3 是這臺有窮自動機接受的語言與 L1 的交。最后 L=L2 U L3 ，它一定是個正則語言。4 、 No

14、nSelfAccepting 是否遞歸集合2002 年 4 月1 . 能被5 整除的字符串是正則集嗎2 . 用圖靈機表示下列字符串。 ， e, a,a*3 .s->ss, s->asb, s->abs, 證明由 s 推得的字符串不可能以 abb 開頭。（可能記憶有誤，具體形式就是這樣）。4 證明不是所有的遞歸可枚舉集都是遞歸的。定理：語言H =: Turing Machine M halts on input string 心不是遞歸的；所以，遞歸語言類是遞歸可枚舉語言類的真子集。2002 年 10 月什么是計算？計算理論研究的內(nèi)容和意義是什么？為什么要使用計算的抽象模1、型

15、？2、 請寫出一個正則表達式，描述下面的語言：在字母表0,1 上，不包含00 子串且以1 結(jié)尾。4、 語言 L=a n:n 是素數(shù)是不是正則語言，是不是上下文無關(guān)的？5、一個 succ(n+1 的組合 Turing 機描述，說出它的作用。 P1276 、什么是 Turing 機的停機問題？它是可判定的么？為什么？H= “ M ”“ w”： Turing 機 M 在輸入 w 上停機 ，ATM = <M,3 >|M 是一個 TM , 且 M 接受3 證明：假設(shè)ATM 是可判定的，下面將由之導出矛盾。設(shè)H 是 ATM 的判定器。 令 M 是一個 TM ， 3是一個串。在輸入<M,

16、3 >上，如果 M 接受 3 ，則 H 就停機且接受 3 ；如果M 不接受 3 ，則 H 也會停機，但拒絕 3 。 換句話說， H 是一個 TM 使得： 接受 如果 M 接受 3H(<M, 3>)=拒絕 如果 M 不接受 3現(xiàn)在來構(gòu)造一個新的圖靈機D ，它以 H 作為子程序。當 M 被輸入 它自己的描述<M>是，TM D就調(diào)用H,以了解M將做什么。一旦得到這個信息， D 就反著做，即：如果 M 接受，它就拒絕；如果M不接受，它就接受。下面是D 的描述。D二"對于輸入<M> ,其中M是一個TM :1) 在輸入 <M,<M>&g

17、t; 上運行 H 。2) 輸出 H 輸出的相反結(jié)論，即，如果H 接受，就拒絕；如果 H 拒絕，就接受。 ”總而言之， 接受 如果 M 不接受 <M>D(<M>)=拒絕 如果 M 接受 <M>當以D的描述<D>作為輸入來運行D自身時，結(jié)果會怎樣呢？我們得到：接受 如果 D 不接受 <M>D(<D>)=拒絕 如果 D 接受 <M>不論 D 做什么，它都被迫相反地做，這顯然是一個矛盾。所以， TM D 和 TM H 都不存在。它是不可判定的。假設(shè)H是遞歸的，那么H “M "： Turing機M在輸入字符串“

18、 M”上停機也 是遞歸 的。H1表示對角化程序的halts （X, X）部分。假設(shè)存在判定 H的Turing機MO ,那么判 定 H1 的 TuringM1 只需要把輸入字符串檢查一個圖靈機是否接受一個給定的串問題。在證明之前，先來證明 ATM 是圖靈可識別的。這樣，定理5.9 表面識別器 確實比判定器更強大。要求TM 在所以輸入上都停機限制了它能夠識別 的語言種類。下面的圖靈機U識別 ATM.U=對于輸入 M, 3 ,其中M是一個TM ,3是一個串：1 ） 在輸入 3 上模擬 M ;2 ） 如果 M 進入接受狀態(tài)，則接受；如果M 進入拒絕狀態(tài)，則拒絕。 ” 注意，如果M在3上循環(huán)，則機器U在

19、輸入M, 3 上循環(huán)，這就是U不判定ATM的原因。假如M 知道自己在3 上不停機，它能拒絕3， 但事實上，它不知道。所以 ATM 有時被稱為停機問題。7 、證明這個問題不可判定：一個 Turing 機半判定的語言等于這樣的 一個語言，這個語言是 w 和 w 的轉(zhuǎn)置的連接。定理：任何遞歸或遞歸可枚舉語言，以及任何遞歸函數(shù)，分別可用隨機存取Turing 判定、 半可判定和計算。1 、 判定下述語言是否正則：包含 aaaaa 子串的語言 L 。2 、 畫出判定下述語言的圖靈機：空集， e ， a 。3 、 用數(shù)學歸納法證明一個上下文無關(guān)語言不包含 ab 子串，語言的描述忘記啦。4 、 證明 H 是非

20、遞歸的。2003 年 4 月1 、 判斷題目， 好像有二十分左右， 都是書上的概念， 譬如：遞歸語言是遞歸可枚舉語言 （錯）， 一個 語言如果是正則的，那么它一定是上下文無關(guān)語言（對） ，如果一個語言是圖靈可識別 的，那么、 . （） 。后面的記不住了。2 、 證明題，第 1 個是要證某種語言是正則語言，第 2 個是證該語言是上下文無關(guān)語言，中 間還有一個是要證明某種語言是非上下文無關(guān)語言（有可能是非正則語言） 。最后一個是證 明該語言是圖靈可判語言。該 題在上幾屆的考題中都曾變換個樣式出現(xiàn)過。3 、 識圖題，畫了一個圖，讓寫出該圖所識別的語言是什么。我記得它是英文參考書上的一 個例題，所識別

21、 的是：不全包含a,b,c 中所有字符的字符串。該題 6 分。4 、我沒做，給出了一個式子，好像是 y=a+b, 讓構(gòu)造出計算該式的圖靈機。這個題目好像也是 6 分。2003 年 10 月1 、5 個判斷，比如例如：1. 也為正則語言。2. 對于兩個任意的正則表達式 R1 和 R2 ，判斷 L(R1)=L(R2) 為不可判定問題。3. xy|x 屬于正則語言 L, y 屬于其補 是正則語言；4. 、存在非遞歸的遞歸可枚舉語言。2、( aAm ) ( bAm ) c (aA2n ) ( b八2n ), m , n? NQ m n± 1,寫出產(chǎn)生它的上下文無關(guān)文法和識別它的確定下推自動機

22、。3) 、 判斷謂詞是否遞歸;設(shè) P(x,y) 為原始遞歸謂詞，請證明 也是原始遞歸謂詞。4) 寫出識別 ( 0An) ( "n ) (2人門 )n 仝 0的圖靈機，和 aAnbAncAn 類似，參考書的答案 有問題！5) L = a 2n+1 | n >=0 不是上下文無關(guān)語言，用泵引理證明 ( 其中， 2 為平方 )在字母表 T=a 上， L = a 2n+1 | n >=0 表示任意一對aa (包括 0 對) 后跟一個 a 的字符串。 ( 即含有奇數(shù)個a 的字 符串。 )6) L 是一上下文無關(guān)文法，任給一正規(guī)文法 R, L? R 可以判定嗎，說明理由。2004 年

23、 4 月1 、 8 個判斷題2 、 證明1 1) L1 是正則語言， L2 是非正則語言，若 L1 和 L2 的交為有限語言，則L1 與 L2 的并為非正則語言。2 2) L1 是正則語言， L2 是非正則語言，若 L1 和 L2 的交為無限語言，則L1 與 L2 的并為正則語言。舉例說明符合條件的L1 和 L23 、有 n 個自然數(shù) x1,x2,.,xn ，問是否存在素數(shù)p使得x(p)Ap=x(1)+x(2)+.+x(p-1)+x(p+1)+.+x(n)(式子類似這樣的)給出算法的描述， 復雜度 ， 并證明屬于 P 類4 、 給出圖靈機的符號表示：該圖靈機計算函數(shù)f(x) ;x 為偶數(shù) f(

24、x)=x/2,x 為奇數(shù) f(x)=x+15 、 用泵定理證明語言 L 不是上下文無關(guān)的 L=w ? (a,b)*:w 不同于WR2004 年 10 月1 、構(gòu)造上下文無關(guān)文法來生成語言L1=a m bncp:m 不等于 n, 且 m n 、 p >1*-(L 1 UL2=a mtfcp:n 不等于 p, 且 m n 、 p >1, 并證明 a,b,cL2)不是上下文無關(guān)的2 、 給出一個Turing 包括轉(zhuǎn)移關(guān)系等根據(jù)給定的Turing 的計算過程求出它所接受的語言L(M); 并構(gòu) 造一個文法來生成 L(M)3 、 一個有關(guān)遞歸的判斷題, 并說出理由 , 有 3 句話。4 、 一

25、個根據(jù)語言描述來判定兩個語言之間關(guān)系的選擇題。如 1 是 2 的真子集 , 2 是 1 的真子集 , 1=2, 1、 2無任何關(guān)系。 2005 年 4 月1 、判斷題2 、 判定下列語言是否為正則語言 , 請具體說出理由L 仁 w1|w ? a,b ,Na(w)-Nb(w) mod 3 工 0 *L2= w1|w ? a,b ,Na(w)-Nb(w) 工 0這里 Na(w) 、 Nb(w) 分別表示 字符串w 中 a,b 的個數(shù)3 、 給出上下文無關(guān)文法生成語言 L3= xcy|2|x|=|y|,x,y ? a,b 證明 L4=a ibjcidj:i,j? N, i,j 三 1不是上下文無關(guān)語

26、言。4 、 證明語言 L5= “ M ” |Turing 在空串 e 上停機 是非遞歸的 , 其中 M 表示Turing M 的編碼。5、給定n個數(shù)，x1,x2, xn,判定是否存在不同的i1,i2 ik,使?jié)M足下列兩個條件：(1) Xi1+Xi2+ Xik=(X1+X2+ Xn)/2(2) Xi1+Xi2+ Xik 不是素數(shù)，給出一個算法，并估計其計算時間，說明這個問題屬于 NP 類，是給算法描述即可。2006 年 4 月1 、 設(shè)上下文無關(guān)語言 L=a *(1)假設(shè) L 為無限語言，且上下文無關(guān)文法 G 生成該語言，即L=L( G)。設(shè)K1為相對于文法G的泵定理常數(shù)，設(shè)r=k。證明下列結(jié)論

27、：對于任意 w? L,如果|w|三k,則wam|n三0 L(2) 對于每個 i ( 0 三 i<r ) ,設(shè) Li= a n |a n ? L, n 三 k, n=l mod r , 證明L= a n|a n? L, n<k U Li(3) 證明如果 L a *為上下文無關(guān)語言，則 L 為正則語言2、設(shè)語言 L1=u v , u、v ? a , b*則，|v| 三 |u| 三 2|v|( 1) 給出一個上下文無關(guān)的文法生成語言 L1( 2)給出一個下推自動機產(chǎn)生語言 L13 、 分別給出滿足條件的語言的例子，或說明其不存在(1)該語言是遞歸的，但是它的補語言非遞歸(2) 該語言是遞歸可枚舉的， 但是它的補語言是遞歸(3) 該語言是遞歸可枚舉的，它的補語言也是遞歸可枚舉不存在(4) 該語言是遞歸可枚舉的，它的補語言卻非遞歸可枚舉若語言是遞歸的，則它是遞歸可枚舉的。 女口： L= anbncn:n 仝 0若 L 是遞歸語言則它的補也是遞歸的。若 L 是遞歸可枚舉語言，則它的補是非遞歸可枚舉的4、語言L稱為前綴圭寸閉(Prefix closed )定義如下：對于任意 w?L 都有 w 的所有前綴均屬于 L 。利用停機問題的規(guī)約證明下列語言。H= "M' |L( M)前綴封閉的5、說明如下問題：ISO= <G1,G2&g