浙江大學(xué)+計(jì)算機(jī)+考博試題+計(jì)算理論及答案

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

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

3、文中，圖靈給“可計(jì)算性”下了一個(gè)嚴(yán)格的數(shù)學(xué)定義，并提出著名的“圖靈機(jī)”(Turing Machine)的設(shè)想?！皥D靈機(jī)”不是一種具體的機(jī)器，而是一種思想模型，可制造一種十分簡單但運(yùn)算能力極強(qiáng)的計(jì)算機(jī)裝置，用來計(jì)算所有能想像得到的可計(jì)算函數(shù)。這個(gè)裝置由下面幾個(gè)部分組成：一個(gè)無限長的紙帶，一個(gè)讀寫頭。（中間那個(gè)大盒子），內(nèi)部狀態(tài)（盒子上的方塊，比如A,B,E,H），另外，還有一個(gè)程序?qū)@個(gè)盒子進(jìn)行控制。這個(gè)裝置就是根據(jù)程序的命令以及它的內(nèi)部狀態(tài)進(jìn)行磁帶的讀寫、移動(dòng)。工作帶被劃分為大小相同的方格，每一格上可書寫一個(gè)給定字母表上的符號。控制器可以在帶上左右移動(dòng)，它帶有一個(gè)讀寫出一個(gè)你期待的結(jié)果。這一理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、語言，則L1與L2的并為正則語言。舉例說明符合條件的L1和L23、有n個(gè)自然數(shù) x1,x2,.,xn，問是否存在素?cái)?shù)p使得x(p)p=x(1)+x(2)+.+x(p-1)+x(p+1)+.+x(n)（式子類似這樣的）給出算法的描述,復(fù)雜度,并證明屬于P類4、給出圖靈機(jī)的符號表示：該圖靈機(jī)計(jì)算函數(shù)f(x) ;x為偶數(shù) f(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=am bncp:m不等于n，且m、n、p >1L2=ambncp:n不等于p，且m、n、p >1,

22、并證明a,b,c*-(L1L2)不是上下文無關(guān)的2、給出一個(gè)Turing包括轉(zhuǎn)移關(guān)系等 根據(jù)給定的Turing的計(jì)算過程求出它所接受的語言L(M);并構(gòu)造一個(gè)文法來生成L(M)3、一個(gè)有關(guān)遞歸的判斷題，并說出理由，有3句話。4、一個(gè)根據(jù)語言描述來判定兩個(gè)語言之間關(guān)系的選擇題。如1是2的真子集，2是1的真子集，1=2，1、2無任何關(guān)系。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的個(gè)數(shù)3、給出上下文無關(guān)文法

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

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