計(jì)算理論考試題庫(kù)及答案

一、選擇題1.以下哪種語(yǔ)言不屬于可判定語(yǔ)言（）A.所有正則語(yǔ)言B.所有上下文無(wú)關(guān)語(yǔ)言C.停機(jī)問(wèn)題對(duì)應(yīng)的語(yǔ)言D.字母表{0,1}上長(zhǎng)度為偶數(shù)的字符串組成的語(yǔ)言答案：C2.圖靈機(jī)的基本組成部分不包括（）A.一條無(wú)限長(zhǎng)的紙帶B.一個(gè)讀寫(xiě)頭C.一個(gè)有限狀態(tài)控制器D.一個(gè)存儲(chǔ)棧答案：D3.若一個(gè)語(yǔ)言\(L\)是遞歸可枚舉的，但不是遞歸的，那么\(L\)是（）A.可判定語(yǔ)言B.半可判定語(yǔ)言C.不可判定語(yǔ)言D.正則語(yǔ)言答案：B4.以下關(guān)于正則表達(dá)式與有限自動(dòng)機(jī)的關(guān)系，正確的是（）A.每個(gè)正則表達(dá)式都能唯一對(duì)應(yīng)一個(gè)確定有限自動(dòng)機(jī)B.每個(gè)有限自動(dòng)機(jī)都能表示為一個(gè)正則表達(dá)式C.正則表達(dá)式描述的語(yǔ)言比有限自動(dòng)機(jī)描述的語(yǔ)言更強(qiáng)大D.有限自動(dòng)機(jī)不能識(shí)別正則表達(dá)式生成的語(yǔ)言答案：B5.給定文法\(G=(V,T,P,S)\)，其中\(zhòng)(V=\{S,A\},T=\{0,1\},P=\{S\to0A,A\to1S,A\to\epsilon\}\)，該文法產(chǎn)生的語(yǔ)言是（）A.包含相同數(shù)量0和1的字符串集合B.以0開(kāi)頭且0和1交替出現(xiàn)的字符串集合C.所有由0和1組成的字符串集合D.空集答案：B二、填空題1.計(jì)算理論中，可計(jì)算函數(shù)可以通過(guò)__________來(lái)精確描述。答案：圖靈機(jī)2.有限自動(dòng)機(jī)分為確定有限自動(dòng)機(jī)（DFA）和__________。答案：非確定有限自動(dòng)機(jī)（NFA）3.若語(yǔ)言\(L\)是可判定的，那么存在一個(gè)圖靈機(jī)\(M\)，對(duì)于任意輸入\(w\in\Sigma^\)，\(M\)總是能__________并給出接受或拒絕的判定。答案：停機(jī)4.上下文無(wú)關(guān)文法\(G=(V,T,P,S)\)中，\(V\)是__________，\(T\)是終結(jié)符集合，\(P\)是產(chǎn)生式集合，\(S\)是開(kāi)始符號(hào)。答案：非終結(jié)符集合5.一個(gè)語(yǔ)言\(L\)是遞歸的當(dāng)且僅當(dāng)\(L\)和\(\overline{L}\)都是__________。答案：遞歸可枚舉的三、簡(jiǎn)答題1.簡(jiǎn)述圖靈機(jī)的工作原理。答案：圖靈機(jī)由一條無(wú)限長(zhǎng)的紙帶、一個(gè)讀寫(xiě)頭和一個(gè)有限狀態(tài)控制器組成。紙帶被劃分成一個(gè)個(gè)方格，每個(gè)方格可以存儲(chǔ)一個(gè)符號(hào)。讀寫(xiě)頭可以在紙帶上左右移動(dòng)，讀取和修改紙帶上的符號(hào)。有限狀態(tài)控制器根據(jù)當(dāng)前的狀態(tài)和讀寫(xiě)頭讀取的符號(hào)，決定讀寫(xiě)頭的動(dòng)作（如向左移動(dòng)、向右移動(dòng)、寫(xiě)入新符號(hào)）以及狀態(tài)的轉(zhuǎn)移。圖靈機(jī)從初始狀態(tài)開(kāi)始，根據(jù)輸入字符串在紙帶上的初始布局，按照上述規(guī)則不斷運(yùn)行，直到進(jìn)入接受狀態(tài)或拒絕狀態(tài)或永遠(yuǎn)不停機(jī)。2.說(shuō)明正則語(yǔ)言和上下文無(wú)關(guān)語(yǔ)言的主要區(qū)別。答案：正則語(yǔ)言可以由正則表達(dá)式、有限自動(dòng)機(jī)描述，其語(yǔ)法結(jié)構(gòu)相對(duì)簡(jiǎn)單，主要處理的是具有線性結(jié)構(gòu)和有限記憶的模式。例如，描述固定模式的電話號(hào)碼格式等。上下文無(wú)關(guān)語(yǔ)言由上下文無(wú)關(guān)文法生成，其描述能力更強(qiáng)，可以處理具有嵌套結(jié)構(gòu)的語(yǔ)言，如編程語(yǔ)言中的表達(dá)式（像算術(shù)表達(dá)式的嵌套括號(hào)結(jié)構(gòu)）。上下文無(wú)關(guān)語(yǔ)言能夠處理一些正則語(yǔ)言無(wú)法處理的更復(fù)雜的語(yǔ)法結(jié)構(gòu)，但仍然有其局限性，對(duì)于一些具有更復(fù)雜語(yǔ)義和依賴關(guān)系的語(yǔ)言無(wú)法準(zhǔn)確描述。3.什么是停機(jī)問(wèn)題？為什么它是不可判定的？答案：停機(jī)問(wèn)題是指：給定一個(gè)圖靈機(jī)\(M\)和一個(gè)輸入字符串\(w\)，判斷圖靈機(jī)\(M\)在輸入\(w\)上是否會(huì)停機(jī)。證明其不可判定通常采用反證法。假設(shè)存在一個(gè)判定停機(jī)問(wèn)題的圖靈機(jī)\(H\)，它可以判斷任意的圖靈機(jī)\(M\)和輸入\(w\)時(shí)\(M\)是否停機(jī)。構(gòu)造一個(gè)新的圖靈機(jī)\(D\)，對(duì)于輸入\(M\)，\(D\)調(diào)用\(H\)來(lái)判斷\(M\)在輸入\(M\)上是否停機(jī)。如果\(H\)判斷\(M\)在輸入\(M\)上停機(jī)，那么\(D\)進(jìn)入死循環(huán)；如果\(H\)判斷\(M\)在輸入\(M\)上不停機(jī)，那么\(D\)停機(jī)。當(dāng)把\(D\)自身作為輸入給\(D\)時(shí)，就會(huì)產(chǎn)生矛盾，所以不存在這樣的圖靈機(jī)\(H\)，即停機(jī)問(wèn)題是不可判定的。四、綜合題1.給定一個(gè)確定有限自動(dòng)機(jī)\(M=(Q,\Sigma,\delta,q_0,F)\)，其中\(zhòng)(Q=\{q_0,q_1,q_2\},\Sigma=\{0,1\},\delta\)如下：\(\delta(q_0,0)=q_1,\delta(q_0,1)=q_2\)\(\delta(q_1,0)=q_0,\delta(q_1,1)=q_2\)\(\delta(q_2,0)=q_2,\delta(q_2,1)=q_0\)\(F=\{q_1\}\)（1）畫(huà)出該有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖。（2）寫(xiě)出該有限自動(dòng)機(jī)接受的語(yǔ)言\(L(M)\)的正則表達(dá)式。答案：（1）狀態(tài)轉(zhuǎn)移圖繪制：-有三個(gè)狀態(tài)\(q_0\)、\(q_1\)、\(q_2\)，\(q_0\)為初始狀態(tài)，\(q_1\)為接受狀態(tài)（用雙圈表示）。-從\(q_0\)出發(fā)，輸入0指向\(q_1\)，輸入1指向\(q_2\)。-從\(q_1\)出發(fā)，輸入0指向\(q_0\)，輸入1指向\(q_2\)。-從\(q_2\)出發(fā)，輸入0保持在\(q_2\)，輸入1指向\(q_0\)。（2）求正則表達(dá)式：設(shè)\(R_{ij}^k\)表示從狀態(tài)\(q_i\)到狀態(tài)\(q_j\)，經(jīng)過(guò)狀態(tài)編號(hào)不超過(guò)\(k\)的路徑所對(duì)應(yīng)的正則表達(dá)式。-初始情況：-\(R_{00}^0=\epsilon\)，\(R_{01}^0=0\)，\(R_{02}^0=1\)-\(R_{10}^0=0\)，\(R_{11}^0=\epsilon\)，\(R_{12}^0=1\)-\(R_{20}^0=\epsilon\)，\(R_{21}^0=\epsilon\)，\(R_{22}^0=\epsilon+0\)-經(jīng)過(guò)\(q_0\)狀態(tài)擴(kuò)展（\(k=0\)到\(k=1\)）：-\(R_{00}^1=R_{00}^0+R_{01}^0(R_{11}^0)^R_{10}^0=\epsilon+0\epsilon^0=\epsilon+00\)-\(R_{01}^1=R_{01}^0(R_{11}^0)^=0\epsilon^=0\)-\(R_{02}^1=R_{02}^0+R_{01}^0(R_{11}^0)^R_{12}^0=1+0\epsilon^1=1+01\)-\(R_{10}^1=R_{10}^0+R_{11}^0(R_{11}^0)^R_{10}^0=0+\epsilon\epsilon^0=0+0=0\)-\(R_{11}^1=R_{11}^0(R_{11}^0)^=\epsilon\epsilon^=\epsilon\)-\(R_{12}^1=R_{12}^0+R_{11}^0(R_{11}^0)^R_{12}^0=1+\epsilon\epsilon^1=1+1=1\)-\(R_{20}^1=R_{20}^0+R_{21}^0(R_{11}^0)^R_{10}^0=\epsilon+\epsilon\epsilon^0=\epsilon+0\)-\(R_{21}^1=R_{21}^0(R_{11}^0)^=\epsilon\epsilon^=\epsilon\)-\(R_{22}^1=R_{22}^0+R_{21}^0(R_{11}^0)^R_{12}^0=\epsilon+0+\epsilon\epsilon^1=\epsilon+0+1\)-經(jīng)過(guò)\(q_2\)狀態(tài)擴(kuò)展（\(k=1\)到\(k=2\)）：-\(R_{00}^2=R_{00}^1+R_{02}^1(R_{22}^1)^R_{20}^1\)-\(R_{01}^2=R_{01}^1+R_{02}^1(R_{22}^1)^R_{21}^1\)-最終得到\(L(M)\)的正則表達(dá)式：從\(q_0\)到\(q_1\)的路徑對(duì)應(yīng)的正則表達(dá)式為\(R_{01}^2\)，經(jīng)過(guò)化簡(jiǎn)可得\((0+1(\epsilon+0+1)^\epsilon)\)，即\((0+1(0+1)^)\)。2.給定上下文無(wú)關(guān)文法\(G=(V,T,P,S)\)，其中\(zhòng)(V=\{S,A\},T=\{a,b\},P=\{S\toaA,A\tobS|\epsilon\}\)（1）給出字符串\(abab\)的最左推導(dǎo)。（2）證明該文法產(chǎn)生的語(yǔ)言\(L(G)\)是\(\{(ab)^n|n\geq1\}\)。答案：（1）最左推導(dǎo)：-\(S\RightarrowaA\)-\(\RightarrowabS\)-\(\RightarrowabaA\)-\(\RightarrowababS\)-\(\Rightarrowabab\)（因?yàn)閈(A\to\epsilon\)最后一步\(S\)推導(dǎo)結(jié)束）（2）證明\(L(G)=\{(ab)^n|n\geq1\}\)：-證明\(L(G)\subseteq\{(ab)^n|n\geq1\}\)：-對(duì)推導(dǎo)步數(shù)進(jìn)行歸納。-基礎(chǔ)情況：當(dāng)推導(dǎo)步數(shù)為1時(shí)，\(S\toaA\)，然后\(A\tobS\)或\(A\to\epsilon\)。若\(A\to\epsilon\)，得到\(a\)，形式為\((ab)^1\)的一部分；若\(A\tobS\)，繼續(xù)推導(dǎo)會(huì)不斷生成\(ab\)的形式。-歸納假設(shè)：假設(shè)在\(k\)步推導(dǎo)內(nèi)生成的字符串都屬于\(\{(ab)^n|n\geq1\}\)。-歸納步驟：在\(k+1\)步推導(dǎo)中，從\(S\)出發(fā)，首先\(S\toaA\)，然后\(A\)要么變?yōu)閈(bS\)要么變?yōu)閈(\epsilon\)。若\(A\tobS\)，那么就會(huì)在原來(lái)推導(dǎo)的基礎(chǔ)上增加\(ab\)這樣一個(gè)片段，仍然保持\((ab)^n\)的形式；若\(A\to\epsilon\)，也符合\((ab)^n\)的形式（例如推導(dǎo)到某一步\(S\to\cdots\toaA\toabS\to\cdots\toabab\)最后\(A\to\epsilon\)結(jié)束推導(dǎo)）。所以\(L(G)\subseteq\{(ab)^n|n\geq1\}\)。-證明\(\{(ab)^n|n\geq1\}\subseteqL(G)\)：-對(duì)于任意\(n\geq1\)，我們來(lái)構(gòu)造字符串\((ab)^n\)的推導(dǎo)。-當(dāng)\(n=1\)時(shí)，\(S\t