湖南大学计算理论引论08级期末试题

计算理论考试题说明：第4题20分，其余每题10分共100分学号：姓名：1.集合A=ZknQxnxxk,,,，证明A是可数的。2.画出识别下列语言的NFA和DFA，字母表都是{0，1}，{w|w的长度是2,3,5,7中的某个数的倍数}3.考虑下面的文法：||aSbSaSS这个文法是歧义的。试证明串aab的两个：1）最左推导；2）语法分析树；4.设上下文无关文法G,将下述CFG转换为乔姆斯基文法。G:SaAa|bBb|AC|aBC|bCCD|DA|B|ab5.证明nkk13是一个完全平方数。6.证明：若A和A均为图灵可识别的，则A为图灵可判定的.7.试证明正规语言在星运算下是封闭的。8.用泵引理证明语言{0n1n0n1n|n0}不是上下文无关的。9.图灵机M的状态图如下：0Lq5RLxRxRq1q2q3R0,R0x,R0R0x,RxRRqrejectqacceptq4xRR在以下输入串上，给出M所进入的格局序列：1.0000002.000000000xL