计算机研究生《计算理论》复习题.doc

1、请你从形式定义、计算过程和对应的语言特点关系等诸方面综合比较DFA、PDA和图灵机 2、对于简单文法（正则语言、上下文无关语言），能够根据其产生式写出其语言 3、正则语言泵引理和上下文无关语言泵引理的理解、相互比较和应用 4、最简DFA、最简PDA的概念；DFA和PDA的简化过程；（带ε和不带ε的）NFA化简成最简DFA的过程 5、图灵机的Golder编码和通用图灵机的编码 6、上下文无关文法的乔姆斯基范式 7、DFA的计算过程 8、上下文无关文法的推导过程以及其歧义相关概念及分析 9、关于四类乔姆斯基语言及其对应的自动机类型特点分析 10、四类乔姆斯基语言的各种运算类型并形式化表示 11、关于CFG和DFA的若干判定问题 12、关于若干渐进符号：同阶渐进符号Θ、大O、小O和大Ω符号的含义和用法 13、请从NP类问题、P类问题、确定型单带TM、确定型多带TM、非确定型TM等角度综述时间复杂性规律 相关例题： 1、请你综合比较DFA、PDA和图灵机 2、请写出下列表达式生成的正则语言 1）设有文法G=(V,T,P,S)，其中V={S,A,B}，T={a,b}，P：S→aB；S→bA；A→bAA；A→a；A→aS；B→b；B→bS；B→aBB 请写出L(G)= 2）设一个有穷自动机M=(Q,(,(,q0,F)，其中Q={q0,q1,q2,q3)， (={0,1}, F={q0}，(如下： ((q0,0)=q2, ((q0,1)=q1, ((q1,0)=q3, ((q1,1)=q0 ((q2,0)=q0, ((q2,1)=q3, ((q3,0)=q1, ((q3,1)=q2 请写出L(M)= 3）设有文法G=({S,A},{a,b,c,d};R,S)，其中R：S(aSd|aAd， A→bAc|bc 请写出L(G)= 3、用泵引理证明下列论点 1）A1={anbncn|n≥0}不是正则语言 2）D={ww|w∈{0，1}*}不是上下文无关语言 4、把下面状态转换图代表的DFA变化成最简DFA 5、设有图灵机M=({q1,q2,q3},{0,1},{0,1,B},(,q1,B,{q2})，其中转移函数(为((q1,1)= (q3,0,R)；((q3,0)=(q1,1,R)；((q3,1)= (q2,0,R)；((q3,B)=(q3,1,L)，试写出其标准编码 6、将文法G转换成乔姆斯基范式，其中G=({S,A},{a,b,c},R,S)，R：S→aS|A, A→bA|c 7、试描述将一台带ε的NFA转换成等价的DFA的过程 8、请你从形式定义、计算过程和对应的语言特点关系等诸方面综合比较DFA、PDA和图灵机 9、对于上下文无关文法G=(V,T,P,S)，其中V={S,A,B}，T={a,b}，P：S→aB|bA；A→a|aS|bAA；B→b|bS|aBB，则 1）请写出L(G)= 2）给出终极符串x=aaabbabbba的最左推导、最右推导和推导树 3）这个文法是否有歧义，如果有歧义，能否给出等价的非歧义文法 10、设有图灵机M=({q1,q2,q3},{0,1},{0,1,B},(,q1,B,{q2})，其中转移函数(为((q1,1)=(q3,0,R)；((q3,0)=(q1,1,R)；((q3,1)=(q2,0,R)；((q3,B)=(q3,1,L)G=({S,A,B},{a,b},R,S)，R：S→bA|aB，A→bAA|aS|a，B→aBB|bS|b|n≥0}不是正则语言 2）B={ab，aabb，…，akbk，…}={akbk|k≥1}(,(,q0,F)，其中Q={q0,q1,q2,q3)， (={0,1}, F={q0}，(如下：((q0,0)=q2, ((q0,1)=q1, ((q1,0)=q3, ((q1,1)=q0, ((q2,0)=q0, ((q2,1)=q3, ((q3,0)=q1, ((q3,1)=q2。请写出L(M)= 2）设有文法G=({S,A},{a,b,c,d};R,S)，其中R：S(aSd|aAd， A→bAc|bc。请写出L(G)= 15、关于泵引理 1）请从内容描述和实质蕴涵两个角度描述并比较有关正则语言和上下文无关语言的两个泵引理 2）证明语言L={aibjcidj|i,j0}不是上下文无关语言 16、设有图灵机M=({q1,q2,q3},{0,1},{0,1,B},(,q1,B,{q2})，其中转移函数(为((q1,1)=(q3,0,R)；((q3,0)=(q1,1,R)；((q3,1)=(q2,0,R)；((q3,B)= (q3,1,L)，试写出其标准编码 17、关于判定问题 1）下面是CFG派生问题ACFG={(G,ω(|G是CFG，ω是串，G派生ω}图灵机高层描述，请用类C语言