《湖南大学计算理论引论08级期末试题(共1页).doc》由会员分享，可在线阅读，更多相关《湖南大学计算理论引论08级期末试题(共1页).doc（1页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
精选优质文档-倾情为你奉上计算理论考试题说明：第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 R L xR xR q1 q2 q3 R 0,R 0x,R 0R 0x,R xR R qreject qaccept q4 xR R在以下输入串上，给出M所进入的格局序列：1. 2.专心-专注-专业