本文分享 WaterCoFire 对 DI32003 - 计算理论在 24/25 学年的期末考试题目的回忆。
This article shares WaterCoFire’s recall of the final exam questions for DI32003 - Theory of Computation in Year 24/25.

考试时间为 2 小时。
Time allowed: 2 hrs.

文末有 PDF 可供下载。
A PDF is available for download at the end of this article.

免责声明 Disclaimer

  • WaterCoFire is not responsible for the authenticity.
    WaterCoFire 不对内容的真实性负责。

  • For reference only. They should not be regarded as predictions of future exam in any way.
    内容仅供参考。这些题目不应在任何方面视作对未来考试情况的预测。

  1. The mathematical formats used may not be compatible with some browsers. Switch browser or download the PDF.
    本文所使用的数学格式可能不与某些浏览器兼容。请切换浏览器或下载 PDF。
  2. Since this is a recall of the questions, some content cannot be provided. This will result in the inability to answer Q1, Q2 b) and Q9. Readers should pay more attention to the examination format of these questions and the knowledge points involved.
    由于本文为对题目的回忆，部分内容无法在此提供。这会导致第一题、第二题 b) 小问以及第九题无法解答。读者应更关注这些题目的考查形式及其涉及到的知识点。

第一题 Q1

考虑给定的 DFA $M$. 对于 $M$ 中的所有状态 $q_0, q_1, q_2, q_3, q_4$，写出一个字符串，使得 $M$ 在处理这个字符串后最终位于该状态.

（注：由于此为回忆，$M$ 的状态转换图略.）

Consider a given DFA $M$. For all states $q_0, q_1, q_2, q_3, q_4$ in $M$, write a string such that $M$ ends up in that state after processing the string.

(Note: Since this is a recall, the transition diagram of $M$ is omitted.)

第二题 Q2

a) 请解释如何将一个 NFA-ϵ 转换为一个标准 NFA.

b) 考虑给定的 NFA-ϵ $M$. 通过将其转换为标准 NFA $M’$，阐述你的思路.

（注：由于此为回忆，$M$ 的状态转换图略.）

a) Explain how to convert a NFA-ϵ to a standard NFA.

b) Consider the given NFA-ϵ $M$. Illustrate your idea by converting it to a standard NFA $M’$.

(Note: Since this is a recall, the transition diagram of $M$ is omitted.)

第三题 Q3

考虑正则语言 $L$. 证明：$L^2 = \lbrace w_1w_2 | w_1 \in L, w_2 \in L \rbrace$ 是正则语言. 不允许直接使用正则语言的性质来证明.

Consider the regular language $L$. Prove that $L^2 = \lbrace w_1w_2 | w_1 \in L, w_2 \in L \rbrace$ is regular. You may not directly use the properties of regular languages to prove this.

第四题 Q4

考虑正则表达式 $(rs)^\ast$ 和 $r^{\ast}s^\ast$. 这两个正则表达式相同吗？请给出证明或给出反例.

Consider the regular expressions $(rs)^\ast$ and $r^{\ast}s^\ast$. Are these two regular expressions the same? Please provide proof or a counterexample.

第五题 Q5

a) 请描述泵引理.

b) 证明：$L = \lbrace 0^n1^m | n > m \rbrace$ 不是正则语言.

a) Describe the Pumping Lemma.

b) Prove that $L = \lbrace 0^n1^m | n > m \rbrace$ is not regular.

第六题 Q6

考虑语言 $L = \lbrace 0^i1^i2^i | i > 0 \rbrace$.

a) 请给出一个能够接受该语言的单向图灵机的实施层面的描述.

b) 解释一个双带图灵机如何能够更快地接受该语言.

Consider the language $L = \lbrace 0^i1^i2^i | i > 0 \rbrace$.

a) Give an implementation-level description of a one-way TM that accepts this language.

b) Explain how a 2-tape TM can accept this language faster.

第七题 Q7

考虑语言 $L_1, L_2, L_3$ 和图灵机 $M_a, M_b, M_c, M_d$. 已知 $M_a$ 和 $M_b$ 并不会对于所有输入均停机，$M_c$ 和 $M_d$ 对于所有输入均会停机，且 $L_1 = L(M_a) = L(M_c)$，$L_2 = L(M_b)$，$L_3 = L(M_d)$.

请指出 $L_1, L_2, L_3$ 中哪些语言是：

a) 部分可判定的？

b) 完全可判定的？

c) 无法判断是部分可判定还是完全可判定的？

并给出解释.

Consider languages $L_1, L_2, L_3$ and TMs $M_a, M_b, M_c, M_d$. It is known that $M_a$ and $M_b$ do not halt on all inputs, while $M_c$ and $M_d$ halt on all inputs, and $L_1 = L(M_a) = L(M_c)$, $L_2 = L(M_b)$, $L_3 = L(M_d)$.

Please indicate which of the languages $L_1, L_2, L_3$ are:

a) Partially decidable?

b) Totally decidable?

c) Impossible to determine whether it is partially decidable or totally decidable?

And give your explanations.

第八题 Q8

a) 给出 NP 类的定义.

b) 给出 NP-Complete 类的定义.

c) 以上两个类之间的关系是什么？

a) Define the NP class.

b) Define the NP-Complete class.

c) What is the relationship between these two classes?

第九题 Q9

考虑六个未知语言 $A, B, C, D, E, F$，一个 NP-Complete 语言 $L_1$ 和一个在 P 类中的语言 $L_2$. 根据给定的它们之间的一些多项式时间归约关系，判断 $A, B, C, D, E, F$ 分别属于的复杂度类.

（注：由于此为回忆，所有归约关系略. 归约关系有大约 8 个，例：$B \propto L_1$，$A \propto C$ 等等. $A, B, C, D, E, F,L_1, L_2$ 在原题中均有自己的名字，如 $Horse$，$Camel$ 等，此处为其别称.）

Consider six unknown languages $A, B, C, D, E, F$, a NP-Complete language $L_1$, and a language $L_2$ in class P. Based on the given polynomial-time reduction relations between them, determine the complexity classes to which $A, B, C, D, E, F$ belong.

(Note: Since this is a recall, all reduction relations are omitted. There are approximately 8 reduction relations, e.g., $B \propto L_1$, $A \propto C$, etc. $A, B, C, D, E, F, L_1, L_2$ all have their own names in the original problem, such as $Horse$, $Camel$, etc., but these are their aliases here.)

下载 Download

所有题目的 PDF（中文版本）：

📥 Download (CN)

PDF of all the questions (in English):

📥 Download (EN)