计算理论考试题库及答案

计算理论考试题库及答案

一、选择题1.以下哪种语言不属于可判定语言（）A.所有正则语言B.所有上下文无关语言C.停机问题对应的语言D.字母表{0,1}上长度为偶数的字符串组成的语言答案：C2.图灵机的基本组成部分不包括（）A.一条无限长的纸带B.一个读写头C.一个有限状态控制器D.一个存储栈答案：D3.若一个语言\(L\)是递归可枚举的，但不是递归的，那么\(L\)是（）A.可判定语言B.半可判定语言C.不可判定语言D.正则语言答案：B4.以下关于正则表达式与有限自动机的关系，正确的是（）A.每个正则表达式都能唯一对应一个确定有限自动机B.每个有限自动机都能表示为一个正则表达式C.正则表达式描述的语言比有限自动机描述的语言更强大D.有限自动机不能识别正则表达式生成的语言答案：B5.给定文法\(G=(V,T,P,S)\)，其中\(V=\{S,A\},T=\{0,1\},P=\{S\to0A,A\to1S,A\to\epsilon\}\)，该文法产生的语言是（）A.包含相同数量0和1的字符串集合B.以0开头且0和1交替出现的字符串集合C.所有由0和1组成的字符串集合D.空集答案：B二、填空题1.计算理论中，可计算函数可以通过__________来精确描述。答案：图灵机2.有限自动机分为确定有限自动机（DFA）和__________。答案：非确定有限自动机（NFA）3.若语言\(L\)是可判定的，那么存在一个图灵机\(M\)，对于任意输入\(w\in\Sigma^\)，\(M\)总是能__________并给出接受或拒绝的判定。答案：停机4.上下文无关文法\(G=(V,T,P,S)\)中，\(V\)是__________，\(T\)是终结符集合，\(P\)是产生式集合，\(S\)是开始符号。答案：非终结符集合5.一个语言\(L\)是递归的当且仅当\(L\)和\(\overline{L}\)都是__________。答案：递归可枚举的三、简答题1.简述图灵机的工作原理。答案：图灵机由一条无限长的纸带、一个读写头和一个有限状态控制器组成。纸带被划分成一个个方格，每个方格可以存储一个符号。读写头可以在纸带上左右移动，读取和修改纸带上的符号。有限状态控制器根据当前的状态和读写头读取的符号，决定读写头的动作（如向左移动、向右移动、写入新符号）以及状态的转移。图灵机从初始状态开始，根据输入字符串在纸带上的初始布局，按照上述规则不断运行，直到进入接受状态或拒绝状态或永远不停机。2.说明正则语言和上下文无关语言的主要区别。答案：正则语言可以由正则表达式、有限自动机描述，其语法结构相对简单，主要处理的是具有线性结构和有限记忆的模式。例如，描述固定模式的电话号码格式等。上下文无关语言由上下文无关文法生成，其描述能力更强，可以处理具有嵌套结构的语言，如编程语言中的表达式（像算术表达式的嵌套括号结构）。上下文无关语言能够处理一些正则语言无法处理的更复杂的语法结构，但仍然有其局限性，对于一些具有更复杂语义和依赖关系的语言无法准确描述。3.什么是停机问题？为什么它是不可判定的？答案：停机问题是指：给定一个图灵机\(M\)和一个输入字符串\(w\)，判断图灵机\(M\)在输入\(w\)上是否会停机。证明其不可判定通常采用反证法。假设存在一个判定停机问题的图灵机\(H\)，它可以判断任意的图灵机\(M\)和输入\(w\)时\(M\)是否停机。构造一个新的图灵机\(D\)，对于输入\(M\)，\(D\)调用\(H\)来判断\(M\)在输入\(M\)上是否停机。如果\(H\)判断\(M\)在输入\(M\)上停机，那么\(D\)进入死循环；如果\(H\)判断\(M\)在输入\(M\)上不停机，那么\(D\)停机。当把\(D\)自身作为输入给\(D\)时，就会产生矛盾，所以不存在这样的图灵机\(H\)，即停机问题是不可判定的。四、综合题1.给定一个确定有限自动机\(M=(Q,\Sigma,\delta,q_0,F)\)，其中\(Q=\{q_0,q_1,q_2\},\Sigma=\{0,1\},\delta\)如下：\(\delta(q_0,0)=q_1,\delta(q_0,1)=q_2\)\(\delta(q_1,0)=q_0,\delta(q_1,1)=q_2\)\(\delta(q_2,0)=q_2,\delta(q_2,1)=q_0\)\(F=\{q_1\}\)（1）画出该有限自动机的状态转移图。（2）写出该有限自动机接受的语言\(L(M)\)的正则表达式。答案：（1）状态转移图绘制：-有三个状态\(q_0\)、\(q_1\)、\(q_2\)，\(q_0\)为初始状态，\(q_1\)为接受状态（用双圈表示）。-从\(q_0\)出发，输入0指向\(q_1\)，输入1指向\(q_2\)。-从\(q_1\)出发，输入0指向\(q_0\)，输入1指向\(q_2\)。-从\(q_2\)出发，输入0保持在\(q_2\)，输入1指向\(q_0\)。（2）求正则表达式：设\(R_{ij}^k\)表示从状态\(q_i\)到状态\(q_j\)，经过状态编号不超过\(k\)的路径所对应的正则表达式。-初始情况：-\(R_{00}^0=\epsilon\)，\(R_{01}^0=0\)，\(R_{02}^0=1\)-\(R_{10}^0=0\)，\(R_{11}^0=\epsilon\)，\(R_{12}^0=1\)-\(R_{20}^0=\epsilon\)，\(R_{21}^0=\epsilon\)，\(R_{22}^0=\epsilon+0\)-经过\(q_0\)状态扩展（\(k=0\)到\(k=1\)）：-\(R_{00}^1=R_{00}^0+R_{01}^0(R_{11}^0)^R_{10}^0=\epsilon+0\epsilon^0=\epsilon+00\)-\(R_{01}^1=R_{01}^0(R_{11}^0)^=0\epsilon^=0\)-\(R_{02}^1=R_{02}^0+R_{01}^0(R_{11}^0)^R_{12}^0=1+0\epsilon^1=1+01\)-\(R_{10}^1=R_{10}^0+R_{11}^0(R_{11}^0)^R_{10}^0=0+\epsilon\epsilon^0=0+0=0\)-\(R_{11}^1=R_{11}^0(R_{11}^0)^=\epsilon\epsilon^=\epsilon\)-\(R_{12}^1=R_{12}^0+R_{11}^0(R_{11}^0)^R_{12}^0=1+\epsilon\epsilon^1=1+1=1\)-\(R_{20}^1=R_{20}^0+R_{21}^0(R_{11}^0)^R_{10}^0=\epsilon+\epsilon\epsilon^0=\epsilon+0\)-\(R_{21}^1=R_{21}^0(R_{11}^0)^=\epsilon\epsilon^=\epsilon\)-\(R_{22}^1=R_{22}^0+R_{21}^0(R_{11}^0)^R_{12}^0=\epsilon+0+\epsilon\epsilon^1=\epsilon+0+1\)-经过\(q_2\)状态扩展（\(k=1\)到\(k=2\)）：-\(R_{00}^2=R_{00}^1+R_{02}^1(R_{22}^1)^R_{20}^1\)-\(R_{01}^2=R_{01}^1+R_{02}^1(R_{22}^1)^R_{21}^1\)-最终得到\(L(M)\)的正则表达式：从\(q_0\)到\(q_1\)的路径对应的正则表达式为\(R_{01}^2\)，经过化简可得\((0+1(\epsilon+0+1)^\epsilon)\)，即\((0+1(0+1)^)\)。2.给定上下文无关文法\(G=(V,T,P,S)\)，其中\(V=\{S,A\},T=\{a,b\},P=\{S\toaA,A\tobS|\epsilon\}\)（1）给出字符串\(abab\)的最左推导。（2）证明该文法产生的语言\(L(G)\)是\(\{(ab)^n|n\geq1\}\)。答案：（1）最左推导：-\(S\RightarrowaA\)-\(\RightarrowabS\)-\(\RightarrowabaA\)-\(\RightarrowababS\)-\(\Rightarrowabab\)（因为\(A\to\epsilon\)最后一步\(S\)推导结束）（2）证明\(L(G)=\{(ab)^n|n\geq1\}\)：-证明\(L(G)\subseteq\{(ab)^n|n\geq1\}\)：-对推导步数进行归纳。-基础情况：当推导步数为1时，\(S\toaA\)，然后\(A\tobS\)或\(A\to\epsilon\)。若\(A\to\epsilon\)，得到\(a\)，形式为\((ab)^1\)的一部分；若\(A\tobS\)，继续推导会不断生成\(ab\)的形式。-归纳假设：假设在\(k\)步推导内生成的字符串都属于\(\{(ab)^n|n\geq1\}\)。-归纳步骤：在\(k+1\)步推导中，从\(S\)出发，首先\(S\toaA\)，然后\(A\)要么变为\(bS\)要么变为\(\epsilon\)。若\(A\tobS\)，那么就会在原来推导的基础上增加\(ab\)这样一个片段，仍然保持\((ab)^n\)的形式；若\(A\to\epsilon\)，也符合\((ab)^n\)的形式（例如推导到某一步\(S\to\cdots\toaA\toabS\to\cdots\toabab\)最后\(A\to\epsilon\)结束推导）。所以\(L(G)\subseteq\{(ab)^n|n\geq1\}\)。-证明\(\{(ab)^n|n\geq1\}\subseteqL(G)\)：-对于任意\(n\geq1\)，我们来构造字符串\((ab)^n\)的推导。-当\(n=1\)时，\(S\t