計算理論導引習題整理

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

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

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

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