計(jì)算理論導(dǎo)引習(xí)題整理

1、第一題：Introduction to theory of computation 第 84 頁(yè):1.6(1 )(2)對(duì)應(yīng)中文教程第三版51頁(yè)1.6(a)(b)題目：畫(huà)出識(shí)別下述語(yǔ)言的DFA狀態(tài)圖。在所有問(wèn)題中字母表均為0,1a.w| w從1開(kāi)始且以0結(jié)束b.w|w含有至少3個(gè)1第二題：Introduction to theory of computation 第 86 頁(yè)，1.16對(duì)應(yīng)中文教程第三版52頁(yè)1.16題目：使用定理1.19給出的構(gòu)造，把下列圖的兩臺(tái)非確定型有窮自動(dòng)機(jī)轉(zhuǎn)換成等價(jià)確實(shí)定型有窮自動(dòng)機(jī)。(b)第三題：Introduction to theory of computatio

2、n 第 86 頁(yè),1.19對(duì)應(yīng)中文教程第三版52頁(yè)題目：使用引理1.29中描述的過(guò)程,把下述正那么表達(dá)式轉(zhuǎn)換成非確定型有窮自動(dòng)機(jī)。a.(0Ul)*000(0Ul)*b.(00)*(ll)U01)* c. 0*第四題：Introduction to theory of computation M 881.29 (a)對(duì)應(yīng)中文教程第三版53頁(yè)1.29 (a)題目：使用泵引理證明下述語(yǔ)言不是正那么的。a.Ai = 0nln2n|n 0解：第五題：Introduction to theory of computation 第 129 頁(yè)，2.6(a)對(duì)應(yīng)中文教程第三版97頁(yè)2.6(a)題目：給出產(chǎn)生下

3、述語(yǔ)言的上下文無(wú)關(guān)文法：a.字母表a,b上a多于b的所有字符串組成的集合。解：第六題：Introduction to theory of computation 第 129 頁(yè)，2.12對(duì)應(yīng)中文教程第三版97頁(yè)2,12題目：用定理2.12中給出的過(guò)程，把聯(lián)系2.3中的CFG G轉(zhuǎn)化成等價(jià)的PDAo2.3題目：設(shè)上下文無(wú)關(guān)文法G：Rf XRX|SS-aTb|bTaT-XTX|X| eXf a|b第七題：Introduction to theory of computation 第 129 頁(yè),2.14對(duì)應(yīng)中文教程第三版98頁(yè)2.14題目：用定理2.6中給出的過(guò)程，把下述CFG轉(zhuǎn)換成等價(jià)的喬姆斯基

4、范式文法 a-*BAB|B| B-00| e第八題：Introduction to theory of computation 第 160 頁(yè)，3.8對(duì)應(yīng)中文教程第三版119頁(yè)3.8題目：下面的語(yǔ)言都是字母表。1上的語(yǔ)言，以實(shí)現(xiàn)層次的描述給出判定這些語(yǔ)言 的圖靈機(jī)：aw| w包含相同個(gè)數(shù)的0和1bw|w所包含的0的個(gè)數(shù)是1的個(gè)數(shù)的兩倍cw|w所包含的0的個(gè)數(shù)不是1的個(gè)數(shù)的兩倍第九題：Introduction to theory of computation 2957.8對(duì)應(yīng)中文教程第三版203頁(yè)7.8題目：令CONNECTED=|G是聯(lián)通的無(wú)向圖。分析節(jié)給出的算法，證明次語(yǔ)言屬于P。第十題：第九題：Introduction to theory of computation H 2957.11對(duì)應(yīng)中文教程第三版203頁(yè)7.12題目