1、第一題：Introduction to theory of computation 第 84 頁:1.6(1 )(2)對(duì)應(yīng)中文教程第三版51頁1.6(a)(b)題目：畫出識(shí)別下述語言的DFA狀態(tài)圖。在所有問題中字母表均為0,1a.w| w從1開始且以0結(jié)束b.w|w含有至少3個(gè)1第二題：Introduction to theory of computation 第 86 頁，1.16對(duì)應(yīng)中文教程第三版52頁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 頁,1.19對(duì)應(yīng)中文教程第三版52頁題目：使用引理1.29中描述的過程,把下述正那么表達(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頁1.29 (a)題目：使用泵引理證明下述語言不是正那么的。a.Ai = 0nln2n|n 0解：第五題：Introduction to theory of computation 第 129 頁，2.6(a)對(duì)應(yīng)中文教程第三版97頁2.6(a)題目：給出產(chǎn)生下

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

4、范式文法 a-*BAB|B| B-00| e第八題：Introduction to theory of computation 第 160 頁，3.8對(duì)應(yīng)中文教程第三版119頁3.8題目：下面的語言都是字母表。1上的語言，以實(shí)現(xiàn)層次的描述給出判定這些語言 的圖靈機(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頁7.8題目：令CONNECTED=|G是聯(lián)通的無向圖。分析節(jié)給出的算法，證明次語言屬于P。第十題：第九題：Introduction to theory of computation H 2957.11對(duì)應(yīng)中文教程第三版203頁7.12題目