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

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

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

3、論基礎(chǔ)1936年，圖靈向倫敦權(quán)威的數(shù)學(xué)雜志投了一篇論文，題為論數(shù)字計(jì)算在決斷難題中的應(yīng)用。在這篇開創(chuàng)性的論文中，圖靈給可計(jì)算性”下了一個(gè)嚴(yán)格的數(shù)學(xué)定義，弁提出著名的圖靈機(jī)”(Turing Machine)的設(shè)想。圖靈機(jī)”不是一種具體的機(jī)器，而是一種思想模型，可制造一種十分簡(jiǎn)單但運(yùn)算能力極強(qiáng)的計(jì)算機(jī)裝置，用來(lái)計(jì)算所有能想像得到的可計(jì)算函數(shù)。這個(gè)裝置由下面幾個(gè)部分組成：一個(gè)無(wú)限長(zhǎng)的紙帶，一個(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)。工作帶被劃分為大小相同的方格，每

4、一格上可書寫一個(gè)給定字母表上的符號(hào)。控制器可以在帶上左右移動(dòng),它帶有一個(gè)讀寫出一個(gè)你期待的結(jié)果。這一理論奠定了整個(gè)現(xiàn)代計(jì)算機(jī)的理論基礎(chǔ)。圖靈機(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、說(shuō)明按喬姆斯基分類，語(yǔ)言、文法、自動(dòng)機(jī)的關(guān)系喬姆斯基將語(yǔ)言定義為，按一定規(guī)律構(gòu)成的句子或符號(hào)串string的有限的或無(wú)限的集合，記為L(zhǎng)o數(shù)目有限的規(guī)則叫文法，記為Go刻畫某類語(yǔ)言的有效手段是文法和自

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

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

7、是遞歸可枚舉語(yǔ)言、上下文相關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言。這四種文法類型依次擁有越來(lái)越嚴(yán)的產(chǎn)生式規(guī)則，同時(shí)文法所能表達(dá)的言也越來(lái)越少。盡管表達(dá)能力比無(wú)限文法和上下文相關(guān)文法要弱，但由于高效率的實(shí)現(xiàn)，四類文法中最重要的上下文無(wú)關(guān)文法和正規(guī)文法。例如對(duì)下文無(wú)關(guān)語(yǔ)言存在算法可以生成高效的LL分析器和LR分析器3、證明HALT(X R,X)不是可計(jì)算的4、(1)、證明遞歸集都是遞歸可枚舉集。(2)、舉例屬于遞歸可枚舉集但不是遞歸集的集合，并證明之。5、(1)、證明L = (a,b)*|a,b的個(gè)數(shù)相同為上下文無(wú)關(guān)語(yǔ)言。(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) 給出圖靈機(jī)的格局、計(jì)算及圖靈機(jī)口計(jì)算函數(shù)f的精確定義。(2 )對(duì)圖靈機(jī)模型而言，church論題是什么？(3 )當(dāng)x是完全平方時(shí)值為 3x,否則為3x+1證明其是原始遞歸函數(shù)。心)二嚴(yán)if)=*12x +1 else設(shè)嘴心O時(shí)LGO艇工的所白因子上利：cr(O)=0.試證切bCO足飾

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

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

11、)= 0 (x,x)+a,a N, 0 (x,y)是編號(hào)為y輸入 為x時(shí)的程序。2001 年 10 月1 、 a, b 上遞歸枚舉語(yǔ)言是否可數(shù)？證明2 、 L=a , b, c 數(shù)目相同的語(yǔ)言 是否 CFL （上下文無(wú)關(guān)）？證明 p95證：不是上下文無(wú)關(guān)的。假設(shè)L 是上下文無(wú)關(guān)的，則它與正則語(yǔ)言a*b*C*的交也是上下文無(wú)關(guān)的。令L1= anbncn:n±0假設(shè) L1 是上下文無(wú)關(guān)語(yǔ)言。取常數(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.有兩種可能他們都導(dǎo)致矛盾。如果 vy 中 a 、 b 、 c 三個(gè)符號(hào)都出現(xiàn)，則 v 和 y 中必有一個(gè)至少含有 abc 中的兩個(gè)符號(hào)。于是uv2xy2z 中 abc 的排列順序不對(duì)，有的 b 在 a 前或 c 在 a 或 b 前。如果 vy 中只出現(xiàn) a、 b、 c 中的一個(gè)或兩個(gè)符號(hào)，貝 Uuv2xy2z中 a 、 b 、 c 的個(gè)數(shù)不相等。?與L1 是上下文無(wú)關(guān)語(yǔ)言假設(shè)矛盾。綜上， L 不是 2 型語(yǔ)言。3 、 被 2, 3 整除的非負(fù)整數(shù)的十進(jìn)制表示的集合是否正則。刀=1 , 2 ,9 , L刀*,令L1是非負(fù)整數(shù)十進(jìn)制表示的集合，容易看到L1=0 U 1 ,

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

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

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

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

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

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

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

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

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

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

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

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

25、個(gè)根據(jù)語(yǔ)言描述來(lái)判定兩個(gè)語(yǔ)言之間關(guān)系的選擇題。如 1 是 2 的真子集 , 2 是 1 的真子集 , 1=2, 1、 2無(wú)任何關(guān)系。 2005 年 4 月1 、判斷題2 、 判定下列語(yǔ)言是否為正則語(yǔ)言 , 請(qǐng)具體說(shuō)出理由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 的個(gè)數(shù)3 、 給出上下文無(wú)關(guān)文法生成語(yǔ)言 L3= xcy|2|x|=|y|,x,y ? a,b 證明 L4=a ibjcidj:i,j? N, i,j 三 1不是上下文無(wú)關(guān)語(yǔ)

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

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