湖南大学计算理论引论08级期末试题(共1页).doc

精选优质文档-倾情为你奉上计算理论考试题说明：第4题20分，其余每题10分共100分 学号： 姓名：1. 集合A=，证明A是可数的。2. 画出识别下列语言的NFA和DFA，字母表都是0，1，w|w的长度是2,3,5,7中的某个数的倍数3. 考虑下面的文法：这个文法是歧义的。试证明串aab的两个：1） 最左推导；2） 语法分析树；4. 设上下文无关文法G, 将下述CFG转换为乔姆斯基文法。G:SaAa|bBb|eAC|aBC|bCCD|eD A|B|ab5. 证明是一个完全平方数。6. 证明：若A和均为图灵可识别的，则A为图灵可判定的.7. 试证明正规语言在星运算下是封闭的。8. 用泵引理证明语言0n1n0n1n |n0不是上下文无关的。xL9. 图灵机M的状态图如下： 0L q5