计算理论导引习题整理

1、第一题：Introduction to theory of computation 第 84 页:1.6(1 )(2)对应中文教程第三版51页1.6(a)(b)题目：画出识别下述语言的DFA状态图。在所有问题中字母表均为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是联通的无向图。分析节给出的算法，证明次语言属于P。第十题：第九题：Introduction to theory of computation H 2957.11对应中文教程第三版203页7.12题目