1、如果一个语言是正则的，那么根据泵引理，存在一个称为______的值，它是该语言中可以被“抽取”字符串的最小长度。
参考答案：泵长度 (pumping length)

解析：见教材P47
泵引理指出，如果一个语言是正则的，则存在一个特定的长度（称为泵长度），使得该语言中所有长度不小于这个长度
的字符串都可以被分成三部分xyz，并且满足特定的条件来允许字符串的“抽取”或重复某部分。

2、泵引理指出，对于任何正则语言 L，存在一个正整数 p（称为泵长度），使得 L 中任何长度不小于 p 的字符串 s 都可以被分成三部分 s = xyz，满足以下条件：
(1) 对任意 i ≥ 0，______ 属于 L
(2) |y| > ______
(3) |xy| ≤ ______

参考答案：
(1) xy^iz
(2) 0
(3) p

解析：见教材P47
这个填空题直接考察了泵引理的三个核心条件。第一个条件说明重复 y 任意次数后得到的字符串仍在语言中；第二个条件确保 y 不是空串；第三个条件限制了 x 和 y 的总长度。

3、如果一个语言是由图灵机识别的，则这个语言被称为________。
参考答案：图灵可识别的
解析：见教材P106
可识别语言是指存在一个图灵机，对于语言中的任何字符串，图灵机在有限时间内停止并接受这个字符串。如果图灵机不能识别一个字符串，则它可能永远运行下去，不会停止。这个定义反映了图灵机作为一种计算模型的识别能力。

4、语言 L 是________，如果存在一个图灵机 M，对于任意输入 w，如果 w ∈ L，则 M 在输入 w 上________；如果 w ∉ L，则 M 在输入 w 上________或________。语言 L 是________，如果存在一个图灵机 M，对于任意输入 w，M 总是停机，并且当且仅当 w ∈ L 时，M ________。

参考答案：
可识别的（或递归可枚举的）、停机并接受、拒绝、永不停机、可判定的（或递归的）、接受

解析：这个填空题考察了可识别语言和可判定语言的定义。可识别语言允许图灵机在非成员输入上可能不停机，而可判定语言要求图灵机对所有输入都停机并给出正确的接受/拒绝决定。

5、图灵机由几个关键部分组成，包括一个无限长的______, 一个读写______, 和一个有限的状态集合，其中包括一个或多个接受状态和一个起始状态。
参考答案：
带子（tape），头（head）

解析：
图灵机的基本组成包括一个无限长的带子，用于存储输入和输出信息；一个读写头，用于在带子上读取和写入符号；以及一个有限的状态集合，用于控制图灵机的操作。带子通常被视为图灵机的记忆体，而状态集合则定义了图灵机的计算逻辑和行为。

6、在计算理论中，如果存在一个算法可以将问题 A 的每个实例转换为问题 B 的一个实例，
且 A 的解可以通过 B 的解容易地获得，我们说问题 A 可以______到问题 B。
如果 A 可归约到 B，且 B 是______的，那么 A 也是______的。
相反，如果 A 是______的，那么 B 也必须是______的。

参考答案：
归约、可判定、可判定、不可判定、不可判定

解析：见教材P136

7、波斯特对应问题是一个______问题。给定一组配对字符串列表 {(x1, y1), (x2, y2), ..., (xn, yn)}，问题是要找到一个索引序列 i1, i2, ..., ik，使得 xi1xi2...xik = yi1yi2...yik。如果存在这样的序列，我们说这个 PCP 实例有______；否则，我们说它______。PCP 的一般形式被证明是______的。

参考答案：
不可判定、解、无解、不可判定

8、波斯特对应问题涉及一个由配对字符串组成的列表。每对字符串可以表示为 (xi, yi)，其中 xi 来自"列表 A"，yi 来自"列表 B"。任务是找到一个非空的索引序列 i1, i2, ..., ik，使得通过按此序列拼接列表 A 中的字符串（xi1xi2...xik）与按同一序列拼接列表 B 中的字符串（yi1yi2...yik）______。

参考答案：完全相同

1、证明：每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。

参考答案：见教材P34

2、例题1.38

参考答案：见教材P48

3、使用泵引理证明语言 L = {a^n b^n c^n | n ≥ 0} 不是正则语言。

参考答案框架：

假设 L 是正则的，则存在泵长度 p。
选择字符串 s = a^p b^p c^p，|s| ≥ p。
根据泵引理，s 可以被分为 xyz，满足泵引理的三个条件。
分析 y 的可能情况：
a) y 只包含 a：xy^2z 将有过多的 a，不在 L 中。
b) y 包含 a 和 b：xy^2z 中 a、b、c 的顺序会被打乱，不在 L 中。
c) y 只包含 b：类似情况 a。
d) y 包含 b 和 c：类似情况 b。
e) y 只包含 c：类似情况 a。
所有情况都导致矛盾，因此假设不成立。
结论：L 不是正则语言。

4、证明：如果语言 L 和它的补语言 L' 都是可识别的，那么 L 是可判定的。
参考答案：见教材P132

参考答案框架：

1、假设 L 和 L' 都是可识别的。
2、存在图灵机 M1 识别 L，M2 识别 L'。
3、构造一个新的图灵机 M：

在输入 w 上同时模拟 M1 和 M2 的运行
如果 M1 接受，M 接受
如果 M2 接受，M 拒绝


4、证明 M 总是停机：

对于任何输入 w，w 要么在 L 中，要么在 L' 中
因此，M1 和 M2 中必有一个会停机并接受


5、证明 M 正确判定 L：

如果 w ∈ L，M1 会接受，所以 M 接受
如果 w ∉ L，那么 w ∈ L'，M2 会接受，所以 M 拒绝


6、结论：M 是一个判定 L 的图灵机，因此 L 是可判定的

解析：这个证明题要求学生理解可识别性和可判定性的区别，并能够构造新的图灵机来证明可判定性。关键是理解如何利用两个可识别语言的图灵机来构造一个总是停机的判定器。

5、证明：PCP是不可判定的。
参考答案：见教材P144

例题1.21

参考答案：见教材P34

2、考虑语言 L = {w | w 是由相同数量的 a、b 和 c 组成的字符串，且所有的 a 都在所有的 b 之前，所有的 b 都在所有的 c 之前}。
(a) 给出 L 中的三个字符串和三个不在 L 中的字符串作为例子。
(b) 使用泵引理证明 L 不是正则语言。
(c) 解释为什么这个语言不能被有限自动机识别。

参考答案：
(a) L 中的字符串：abc, aabbcc, aaabbbccc
不在 L 中的字符串：acb, abbc, aabcbc
(b) 证明框架类似于上面的证明题，但选择 s = a^p b^p c^p
参考答案框架：
1、假设 L 是正则的：
这是一个反证法的开始。我们假设 L 是正则的，目的是最终得到一个矛盾。
2、选择字符串 s = a^p b^p c^p：

p 是泵引理保证存在的泵长度。
我们选择这个字符串是因为它恰好在 L 中，且长度足够长（≥ p）。

3、根据泵引理，s 可以被分为 xyz：

这意味着 s 可以被分成三部分：x, y, 和 z。
泵引理说，对任意 i ≥ 0，xy^iz 都应该在 L 中。
另外，|xy| ≤ p 且 |y| > 0。

4、分析 y 的可能情况：
这是证明的关键部分。我们考虑 y 可能的所有情况，并说明每种情况都会导致矛盾。

a) y 只包含 a：
如果 y = a^k（k > 0），那么 xy^2z = a^(p+k) b^p c^p。
这个字符串不在 L 中，因为 a 的数量多于 b 和 c。
b) y 包含 a 和 b：
如果 y = a^k b^m（k > 0, m > 0），那么 xy^2z 会包含 ...abab... 的模式。
这违反了 L 中所有 a 都在所有 b 之前的要求。
c) y 只包含 b：
类似情况 a，xy^2z 中 b 的数量会多于 a 和 c。
d) y 包含 b 和 c：
类似情况 b，会出现 ...bcbc... 的模式，违反了 L 的定义。
e) y 只包含 c：
类似情况 a，c 的数量会多于 a 和 b。
5、所有情况都导致矛盾：
我们已经证明，无论如何选择 y，总会得到一个不在 L 中的字符串。
这与泵引理说的 "xy^iz 应该总在 L 中" 相矛盾。
6、结论：
由于我们从 "L 是正则的" 这个假设出发，得到了矛盾，
所以原假设必定是错误的。因此，L 不是正则语言。

这个证明的核心思想是：正则语言无法 "计数" 和 "比较" 不同字母的数量。通过泵引理，我们展示了任何试图识别这种语言的有限自动机都会在处理足够长的字符串时失败。

(c) 有限自动机无法"计数"和"比较"不同字母的数量。它需要无限的状态来记住已经看到的 a、b、c 的数量，这超出了有限自动机的能力。

3、解释可识别语言与可判定语言的区别，并给出一个可识别但不可判定语言的例子。
答案：可识别语言是指存在一个图灵机，对于语言中的任何字符串，如果字符串属于该语言，图灵机最终会停止并接受它。
但对于不属于该语言的字符串，图灵机可能永远不会停止。而可判定语言要求存在一个图灵机，对于任何输入，
该机器都能在有限时间内决定该字符串是否属于语言，无论结果是接受还是拒绝。

例子：Atm等

4、考虑以下语言：
L1 = {<M> | M 是一个在空输入上停机的图灵机}
L2 = {<M> | M 是一个在空输入上接受的图灵机}
L3 = {<M> | M 是一个在所有输入上都停机的图灵机}

(a) 对于每种语言，判断它是可识别的、可识别的补语言、还是可判定的。
(b) 简要解释你的判断理由。
(c) 对于可识别但不可判定的语言，简述为什么构造判定器会失败。

参考答案：
(a)
L1: 可识别的
L2: 可识别的
L3: 既不可识别也不是可识别的补语言（即不可判定）
(b) 
L1: 可以构造一个图灵机模拟 M 在空输入上的运行，如果 M 停机则接受。
L2: 类似 L1，但只在 M 停机并接受时才接受。
L3: 这是著名的停机问题的变体，是不可判定的。
(c) 对于 L1 和 L2，无法构造判定器，因为无法在有限时间内确定一个图灵机是否会在空输入上无限运行。
这需要解决停机问题，而停机问题是不可判定的。

5、设计一个图灵机 M，它能接受语言 L = {w#w | w ∈ {0,1}*}，其中 # 是一个特殊符号，不属于 {0,1}。

(a) 给出图灵机 M 的形式化定义，包括状态集、输入字母表、纸带字母表和转移函数。
(b) 简要描述 M 的工作过程。
(c) 说明为什么这个语言不能被 DFA 或 PDA（下推自动机）识别，但可以被图灵机识别。
参考答案：
(a) 形式化定义（简化版）：
M = (Q, Σ, Γ, δ, q0, qaccept, qreject), 其中
Q = {q0, q1, q2, q3, qaccept, qreject}
Σ = {0, 1, #}
Γ = {0, 1, #, □【带子上的空白符号】, X}
q0 是初始状态
转移函数 δ 的部分定义：

δ(q0, 0) = (q0, X, R)  // 标记第一个 0 并向右移动
δ(q0, 1) = (q0, X, R)  // 标记第一个 1 并向右移动
δ(q0, #) = (q1, #, R)  // 遇到 # 转到状态 q1
... （其他转移根据需要定义）

(b) 工作过程：

从左到右扫描，将第一个 w 中的每个符号标记为 X
遇到 # 后，继续向右移动
比较第二个 w 中的每个符号与之前标记的符号
如果所有符号都匹配，并且长度相同，则接受；否则拒绝

(c) 解释：

DFA 无法识别此语言，因为它需要无限的存储来记住第一个 w
PDA 也无法识别，因为它只能比较相邻的部分，而不能在任意距离上比较
图灵机可以识别，因为它可以多次遍历输入，标记已读取的部分，并在任意位置进行比较

6、题目：考虑以下两个问题：

问题 A（图的哈密顿回路问题）：给定一个无向图 G，判断 G 是否存在哈密顿回路。
问题 B（图的哈密顿路径问题）：给定一个无向图 G，判断 G 是否存在哈密顿路径。

(a) 简要解释哈密顿回路和哈密顿路径的区别。
(b) 证明问题 A 可以归约到问题 B。
(c) 如果已知问题 B 是 NP 完全的，我们能得出什么结论？

参考答案：
(a) 哈密顿回路是一条经过图中所有顶点恰好一次并回到起点的闭合路径。
哈密顿路径是一条经过图中所有顶点恰好一次的路径，但不需要回到起点。
(b) 归约步骤：

给定图 G，构造新图 G'：在 G 中选择任意顶点 v，添加新顶点 v'，连接 v 和 v'。
在 G' 中寻找哈密顿路径。
G 有哈密顿回路，当且仅当 G' 有以 v 或 v' 为端点的哈密顿路径。

(c) 结论：

问题 A 至少和问题 B 一样难。
问题 A 也是 NP 难的。
如果能证明问题 A 在 NP 中，那么问题 A 也是 NP 完全的。