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

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

2、補、交運算下是封閉的。每一臺非確定型有窮自動機都等價于某一臺確定型有窮自動機。一個語言是正則的當且僅當它被有窮自動機接受。正則表達式：稱R是一個正則表達式，如果R是1）a，這里a是字母表中的一個元素。2），只包含一個字符串空串的語言3），不包含任何字符串的語言4)(R1R2),這里R1和R2是正則表達式5）(R10R2),這里R1和R2是正則表達式6）(R1*),這里R1*是正則表達式一個語言是正則的當且僅當可以用正則表達式描述。2000年4月1、根據(jù)圖靈機理論,說明現(xiàn)代計算機系統(tǒng)的理論基礎。 1936年，圖靈向倫敦權威的數(shù)學雜志投了一篇論文，題為論數(shù)字計算在決斷難題中的應用。在這篇開創(chuàng)性的論

3、文中，圖靈給“可計算性”下了一個嚴格的數(shù)學定義，并提出著名的“圖靈機”(Turing Machine)的設想?！皥D靈機”不是一種具體的機器，而是一種思想模型，可制造一種十分簡單但運算能力極強的計算機裝置，用來計算所有能想像得到的可計算函數(shù)。這個裝置由下面幾個部分組成：一個無限長的紙帶，一個讀寫頭。（中間那個大盒子），內部狀態(tài)（盒子上的方塊，比如A,B,E,H），另外，還有一個程序對這個盒子進行控制。這個裝置就是根據(jù)程序的命令以及它的內部狀態(tài)進行磁帶的讀寫、移動。工作帶被劃分為大小相同的方格，每一格上可書寫一個給定字母表上的符號?？刂破骺梢栽趲献笥乙苿樱鼛в幸粋€讀寫出一個你期待的結果。這一理

4、論奠定了整個現(xiàn)代計算機的理論基礎?！皥D靈機”更在電腦史上與“馮·諾依曼機”齊名，被永遠載入計算機的發(fā)展史中。圖靈機在理論上能模擬現(xiàn)代數(shù)字計算機的一切運算,可視為現(xiàn)代數(shù)字計算機的數(shù)學模型。實際上,一切"可計算"函數(shù)都等價于圖靈機可計算函數(shù),而圖靈機可計算函數(shù)類又等價于一般遞歸函數(shù)類。2、說明按喬姆斯基分類，語言、文法、自動機的關系喬姆斯基將語言定義為，按一定規(guī)律構成的句子或符號串string的有限的或無限的集合，記為L。數(shù)目有限的規(guī)則叫文法，記為G。刻畫某類語言的有效手段是文法和自動機。文法與自動機的關系:形式文法是從生成的角度來描述語言的,而自動機是從識別的角度來

5、描述語言的.文法和自動機是形式語言理論的基本內容。對某種語言來說,如果存在一個該語言的生成過程,就一定存在一個對于它的識別過程.就描述語言來講,形式語言和自動機是統(tǒng)一的.文法在形式上定義為四元組：G（VN,VT,S,P）,VN是非終極符號，VT是終極符號，S是VN中的初始符號，P是重寫規(guī)則。n 文法是定義語言的一個數(shù)學模型，而自動機可看作是語言的識別系統(tǒng)。n 對于一個文法產(chǎn)生的語言，可以構造相應自動機接受該語言：一個自動機接受的語言，可以構造對應的文法產(chǎn)生該語言。一定類型的自動機和某種類型的文法具有等價性。 2、喬姆斯基根據(jù)轉換規(guī)則將文法分作4類。每類文法的生成能力與相應的語言自動機（識別語言

6、的裝置）的識別能力等價，即4類文法分別與4種語言自動機對應：類型文法自動機0型無限制文法圖靈機1型上下文有關文法線性有界自動機2型上下文無關文法后進先出自動機3型有限狀態(tài)的正則文法有限自動機最常見文法的分類系統(tǒng)是 諾姆·喬姆斯基 于 1956年 發(fā)展的 喬姆斯基譜系 ，這個分類譜系把所有的文法分成四類型： 無限制文法 、 上下文相關文法 、 上下文無關文法 和 正規(guī)文法 。四類文法對應的語言類分別是 遞歸可枚舉語言 、 上下文相關語言 、 上下文無關語言 和 正規(guī)語言 。這四種文法類型依次擁有越來越嚴的產(chǎn)生式規(guī)則，同時文法所能表達的言也越來越少。盡管表達能力比無限文法和上下文相關文法

7、要弱，但由于高效率的實現(xiàn)，四類文法中最重要的上下文無關文法和正規(guī)文法。例如對下文無關語言存在算法可以生成高效的 LL 分析器 和 LR 分析器 。3、證明HALT(XR,X)不是可計算的。4、（1）、證明遞歸集都是遞歸可枚舉集。 （2）、舉例屬于遞歸可枚舉集但不是遞歸集的集合，并證明之。5、（1）、證明L(a,b)*|a,b的個數(shù)相同為上下文無關語言。 （2）、并證明其不是正則的。P56假設L是正則的，則根據(jù)在交下的封閉性，La*b*也是封閉的，而后者正好是L1= aibi:i0,假設L1是正則的，則存在滿足泵引理的整數(shù)n?？紤]字符串w= anbnL。根據(jù)定理可以寫成w=xyz使得|xy|n，

8、且ye，即y=ai ，其中i0.但是xz= an-ibnL，與定理矛盾。2000年10月1、（1）給出圖靈機的格局、計算及圖靈機計算函數(shù)f的精確定義。(2 ) 對圖靈機模型而言，church論題是什么？（3）當x是完全平方時值為3x，否則為3x+1證明其是原始遞歸函數(shù)。2、證明（X，X）是不可計算的。3、證明L=ambn|m,n>0,mn是上下文無關的，但不是正則的。利用上下文無關語言在并、連接、Kleene星號下是封閉的。正則語言在交運算下封閉。4、A為有窮字母表，L是A*的無窮子集，（1）證明存在無窮序列0,1,2，它由L的所有字組成，每個字恰好在其中只出現(xiàn)一次。（2）是否存在從L構

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

10、上遞歸枚舉語言是否可數(shù)？證明2、L=a，b，c數(shù)目相同的語言是否CFL（上下文無關）？證明p95證：不是上下文無關的。假設L是上下文無關的，則它與正則語言a* b* c*  的交也是上下文無關的。令L1=anbncn:n0假設L1是上下文無關語言。 取常數(shù)p，ap bp cp ,3pp 將寫成uvxyz使得v或y不是空串且uvixyizL1 I=0,1,2其中xy1 且 xuyp.有兩種可能他們都導致矛盾。如果vy中a、b、c三個符號都出現(xiàn)，則v和y中必有一個至少含有abc中的兩個符號。于是uv2xy2z中abc的排列順序不對，有的b在a前或c在a或b前。如果vy中只出現(xiàn)a、b、c中

11、的一個或兩個符號，則uv2xy2z中a、b、c的個數(shù)不相等。 與L1是上下文無關語言假設矛盾。綜上，L不是2型語言。3、被2，3整除的非負整數(shù)的十進制表示的集合是否正則。=1，2，9，L*，令L1是非負整數(shù)十進制表示的集合，容易看到L1=01，2，9*，由于L1是用正則表達式表示的，故它是一個正則語言。令L2是可以被2整除的非負整數(shù)的十進制表示的集合。L2正好是以0，2，4，6，8結尾的L1的成員組成的集合，即L2=L1*0，2，4，6，8，根據(jù)正則語言在交運算下封閉原則，故L2也是一個正則語言。令是可以被3整除的非負整數(shù)的十進制表示的集合.一個數(shù)可以被3整除當且僅當它的數(shù)字之和可以被3整除。

12、構造一臺有窮自動機，用它的有窮控制器保存輸入數(shù)字的模3和。L3是這臺有窮自動機接受的語言與L1的交。最后L=L2L3，它一定是個正則語言。4、NonSelfAccepting是否遞歸集合2002年4月1        能被5整除的字符串是正則集嗎2        用圖靈機表示下列字符串。，e，a,a*3        s->ss, s->asb, s->abs, 證明由s推得的字符串不可能以abb開

13、頭。（可能記憶有誤，具體形式就是這樣）。 4 證明不是所有的遞歸可枚舉集都是遞歸的。定理：語言不是遞歸的；所以，遞歸語言類是遞歸可枚舉語言類的真子集。2002年10月1、        什么是計算？計算理論研究的內容和意義是什么？為什么要使用計算的抽象模型？2、        請寫出一個正則表達式，描述下面的語言：在字母表0,1上，不包含00子串且以1結尾。4、語言L=an:n是素數(shù)是不是正則語言，是不是上下文無關的？5、一個succ(n+1)的組合Turing機描述，說出它

14、的作用。P1276、什么是Turing機的停機問題？它是可判定的么？為什么？ H=“M”“w”：Turing機M在輸入w上停機，ATM <M, >|M是一個TM， 且M接受證明：假設ATM是可判定的，下面將由之導出矛盾。設H是ATM的判定器。 令M是一個TM， 是一個串。在輸入<M, >上，如果M接受，則H就停機且接受；如果M不接受，則H也會停機，但拒絕。 換句話說，H是一個TM使得：接受如果M接受H(<M, >)=拒絕如果M不接受 現(xiàn)在來構造一個新的圖靈機D，它以H作為子程序。當M被輸入 它自己的描述<M>是，TM D就調用H，以了解M將做什么

15、。一旦 得到這個信息，D就反著做，即：如果M接受，它就拒絕；如果M 不接受，它就接受。下面是D的描述。D”對于輸入<M>，其中M是一個TM： 1) 在輸入<M,<M>>上運行H。 2) 輸出H輸出的相反結論，即，如果H接受，就拒絕； 如果H拒絕，就接受?！笨偠灾?，接受如果M不接受<M>D(<M>)=拒絕如果M接受<M>當以D的描述<D>作為輸入來運行D自身時，結果會怎樣呢？我們得到：接受如果D不接受<M>D(<D>)=拒絕如果D接受<M>不論D做什么，它都被迫相反地做，這顯

16、然是一個矛盾。所以，TM D和TM H都不存在。它是不可判定的。假設H是遞歸的，那么H1=“M”：Turing機M在輸入字符串“M”上停機也是遞歸的。H1表示對角化程序的halts（X，X）部分。假設存在判定H的Turing機M0，那么判定H1的TuringM1只需要把輸入字符串檢查一個圖靈機是否接受一個給定的串問題。在證明之前，先來證明ATM是圖靈可識別的。這樣，定理5.9表面識別器確實比判定器更強大。要求TM在所以輸入上都停機限制了它能夠識別的語言種類。下面的圖靈機U識別ATM.U=“對于輸入<M, >,其中M是一個TM， 是一個串：1) 在輸入上模擬M ；2) 如果M進入接受

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

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

19、符串。該題6分。4、我沒做，給出了一個式子，好像是y=a+b,讓構造出計算該式的圖靈機。這個題目好像也是6分。2003年10月1、5個判斷，比如例如：   1.  也為正則語言。 2. 對于兩個任意的正則表達式R1和R2，判斷L(R1)=L(R2)為不可判定問題。 3、xy|x屬于正則語言L，y屬于其補是正則語言； 4、存在非遞歸的遞歸可枚舉語言。2、（am）（bm）c（a2n）（b2n），m，nNm、n1，寫出產(chǎn)生它的上下文無關文法和識別它的確定下推自動機。3、判斷謂詞是否遞歸;設P(x,y)為原始遞歸謂詞，請證明 也是原始遞歸謂詞。4、寫出識別（0n

20、）（1n）（2n） n0的圖靈機，和anbncn類似，參考書的答案有問題！5）L = a 2n+1 | n >=0  不是上下文無關語言，用泵引理證明（其中，2為平方）n 在字母表T=a上，L = a 2n+1 | n >=0 n 表示任意一對aa (包括0對) 后跟一個a的字符串。（即含有奇數(shù)個a的字符串。）6）L是一上下文無關文法，任給一正規(guī)文法R，LR可以判定嗎，說明理由。2004年4月1、8個判斷題2、證明（1）L1是正則語言，L2是非正則語言，若L1和L2的交為有限語言，則L1與L2的并為非正則語言。（2）L1是正則語言，L2是非正則語言，若L1和L2的交為無限

21、語言，則L1與L2的并為正則語言。舉例說明符合條件的L1和L23、有n個自然數(shù) x1,x2,.,xn，問是否存在素數(shù)p使得x(p)p=x(1)+x(2)+.+x(p-1)+x(p+1)+.+x(n)（式子類似這樣的）給出算法的描述,復雜度,并證明屬于P類4、給出圖靈機的符號表示：該圖靈機計算函數(shù)f(x) ;x為偶數(shù) f(x)=x/2,x為奇數(shù) f(x)=x+15、用泵定理證明語言L不是上下文無關的 L=w(a,b)*:w不同于WR2004年10月1、構造上下文無關文法來生成語言 L1=am bncp:m不等于n，且m、n、p >1L2=ambncp:n不等于p，且m、n、p >1,

22、并證明a,b,c*-(L1L2)不是上下文無關的2、給出一個Turing包括轉移關系等 根據(jù)給定的Turing的計算過程求出它所接受的語言L(M);并構造一個文法來生成L(M)3、一個有關遞歸的判斷題，并說出理由，有3句話。4、一個根據(jù)語言描述來判定兩個語言之間關系的選擇題。如1是2的真子集，2是1的真子集，1=2，1、2無任何關系。2005年4月1、判斷題2、判定下列語言是否為正則語言，請具體說出理由L1=w1|wa,b* ,Na(w)-Nb(w) mod 3 0L2= w1|wa,b* ,Na(w)-Nb(w)0這里Na(w)、Nb(w)分別表示字符串w中a,b的個數(shù)3、給出上下文無關文法

23、生成語言 L3=xcy|2|x|=|y|,x,ya,b*證明L4=aibjcidj:i,jN, i,j 1不是上下文無關語言。4、證明語言L5=“M”|Turing在空串e上停機是非遞歸的，其中M表示Turing M的編碼。5、給定n個數(shù)，x1,x2,xn,判定是否存在不同的i1,i2ik,使?jié)M足下列兩個條件： （1）Xi1+Xi2+Xik=(X1+X2+Xn)/2(2) Xi1+Xi2+Xik不是素數(shù)，給出一個算法，并估計其計算時間，說明這個問題屬于NP類，是給算法描述即可。2006年4月1、設上下文無關語言L=a* （1）假設L為無限語言，且上下文無關文法G生成該語言，即L=L（

24、G）。設K1為相對于文法G的泵定理常數(shù)，設r=k。證明下列結論：對于任意wL，如果|w|k，則wam |n0L（2）對于每個i（0i<r）,設Li= an |anL，nk，n=I mod r，證明L= an |anL，n<k Li （3）證明如果L a*為上下文無關語言，則L為正則語言2、設語言L1=uv，u、va，b*則，|v|u|2|v| （1）給出一個上下文無關的文法生成語言L1（2）給出一個下推自動機產(chǎn)生語言L13、分別給出滿足條件的語言的例子，或說明其不存在(1)該語言是遞歸的，但是它的補語言非遞歸（2）該語言是遞歸可枚舉的， 但是它的補語言是遞歸（3）該語言是遞歸可枚舉的，它的補語言也是遞歸可枚舉 不存在（4）該語言是遞歸可枚舉的，它的補語言卻非遞歸可枚舉 若語言是遞歸的，則它是遞歸可枚舉的。 如：L=anbncn:n0若L是遞歸語言則它的補也是遞歸的。若L是遞歸可枚舉語言，則它的補是非遞歸可枚舉的。4、語言L稱為前綴封閉（Prefix closed）定義如下：對于任意wL都有w的所有前綴均屬于。利用停機問題的規(guī)約證明下列語言?！啊保ǎ榍熬Y封閉的、說明如下問題： <G1,G2>|無向圖i=(Vi,Ei)(i=1,2)同構是的。（只需