1 第 9 章教材习题：题意释义与通用解题方法

本节不是逐题完整解答。 它为每个教材编号习题提供经页面核验的题意释义（Problem）、主题标签（Topic），以及本章层面的通用解题方法导引。本公开仓库不分发教材原图、转移表、边权与长表达式，因此具体数值、状态名与表达式需结合教材对应原页数据自行推导。同一类题的“方法导引”会重复出现，它说明的是解题思路，而不是该题的具体答案。

本章共收录 25 个教材编号习题。

1.1 习题 9.1.1

Source: textbook PDF p.271

Problem（教材题意释义）

根据教材的枚举顺序写出 w_37、w_100 等二进制串。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

按题目定义直接建立形式化对象，并使用本章相应的标准构造或归纳证明。先写清楚输入、目标和不变量，再逐步给出构造；证明正确性时分别证明“构造出的对象不会接受/生成错误实例”和“每个合法实例都能被接受/生成”。 若题目是算法题，还要说明停机性与渐近复杂度；若是反例题，优先寻找最短、结构最简单的反例。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.2 习题 9.1.2

Source: textbook PDF p.271

Problem（教材题意释义）

为图 8-9 的 TM 写出一种合法二进制编码。

Topic

TM

方法导引（通用，非本题具体答案）

把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.3 习题 9.1.3

Source: textbook PDF p.272

Problem（教材题意释义）

对两个与对角语言类似的语言，用对角化证明没有 TM 接受它们。

Topic

TM

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.4 习题 9.1.4

Source: textbook PDF p.272

Problem（教材题意释义）

给任意有限输入字母表的 TM 建立统一整数编码方案。

Topic

TM

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.5 习题 9.2.1

Source: textbook PDF p.277

Problem（教材题意释义）

证明停机问题是 RE 但不是递归语言。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.6 习题 9.2.2

Source: textbook PDF p.277

Problem（教材题意释义）

分析教材给出的 Ackermann/递归函数定义，计算若干值并解释为何递归函数概念有用。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.7 习题 9.2.3

Source: textbook PDF p.278

Problem（教材题意释义）

给多带 TM 枚举完全平方数、素数以及通用语言 L_u 的带内容策略。

Topic

TM

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.8 习题 9.2.4

Source: textbook PDF p.278

Problem（教材题意释义）

若 L1,…,Lk 两两不交、并为 Σ*，且每个 Li 都 RE，证明每个 Li 都递归。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.9 习题 9.2.5

Source: textbook PDF p.278

Problem（教材题意释义）

设 L RE 而补非 RE，分析 {0w:w∈L}∪{1w:w∉L} 属于递归/RE/非RE 哪一类。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.10 习题 9.2.6

Source: textbook PDF p.278

Problem（教材题意释义）

判断 RE/递归语言对并、交、连接、星、同态、逆同态等运算的封闭性。

Topic

封闭

方法导引（通用，非本题具体答案）

从已有自动机/文法构造新的识别器。对商与导数，保留原 DFA 的转移图并改变接受条件或起始集合；对 init，把能到达原接受态的状态设为接受态；对 cycle 可猜测切分点并用有限状态记录两个阶段。 对 half/alt 等操作，关键是同时模拟原自动机并在有限控制中记录位置奇偶或同步关系。 若题目要求反例，则选一个已知非正则/非 CFL 的目标语言，并构造简单语言使该运算结果恰好等于目标语言，从封闭性矛盾得证。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.11 习题 9.3.1

Source: textbook PDF p.285

Problem（教材题意释义）

证明“接受所有回文输入”的 TM 编码集合不可判定。

Topic

TM；不可判定

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.12 习题 9.3.2

Source: textbook PDF p.285

Problem（教材题意释义）

分析带“候状态/哨状态”并按状态类型吹哨的 BWTM，证明某输入上是否吹哨不可判定。

Topic

TM；不可判定

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.13 习题 9.3.3

Source: textbook PDF p.285

Problem（教材题意释义）

证明从空白带开始最终写下 1 的 TM 编码语言不可判定。

Topic

TM；不可判定

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.14 习题 9.3.4

Source: textbook PDF p.285

Problem（教材题意释义）

对 Rice 定理推出的若干性质，进一步判断对应语言是 RE 还是非 RE。

Topic

Rice

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.15 习题 9.3.5

Source: textbook PDF p.285

Problem（教材题意释义）

给定 (M1,M2,k)，L(M1)∩L(M2) 至少含 k 个串；证明该语言 RE 但非递归。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.16 习题 9.3.6

Source: textbook PDF p.285

Problem（教材题意释义）

证明若干“机器编码集合”可判定：最终写非空白、永不左移、每格最多扫描一次等。

Topic

按教材定义构造 + 正确性证明

方法导引（通用，非本题具体答案）

选定统一的二进制自描述编码：状态、带符号和方向分别用正整数编号，再用 0 作为字段分隔符、11 或其他前缀码作为结构边界。 只需保证编码集合可判定且解码唯一；任意有限字母表都可先编号后编码。对 w_i 的枚举，按长度优先再按字典序，把 i 与二进制串的偏移关系写出后直接计算。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.17 习题 9.3.7

Source: textbook PDF p.285

Problem（教材题意释义）

证明若干 TM 性质不是 RE：从某输入不停止、两个语言交为空、语言连接等关系。

Topic

TM

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.18 习题 9.3.8

Source: textbook PDF p.285

Problem（教材题意释义）

把四类“所有输入都停/都不停/至少一个停/至少一个不停”的 TM 编码分类为递归、RE非递归或非RE。

Topic

TM

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.19 习题 9.4.1

Source: textbook PDF p.294

Problem（教材题意释义）

判断教材给出的三个 PCP 实例是否有解，并给出/排除匹配序列。

Topic

PCP

方法导引（通用，非本题具体答案）

把教材页中的状态、边、权值或产生式先完整抄成一个有限表，然后严格按本章算法逐步计算；不要凭图形直觉跳步。 本题的可复现做法是：①列出源对象；②执行相应算法（状态消除/可区分表/PDA 的 ID 推演/CFG 推导/PCP 搜索等）；③每一步记录新状态、集合或配置；④用接受条件或不变量核对最终结果。 由于公开版不直接复制教材图表，精确的状态名、边权和表项以所标 PDF 页为准；算法步骤在这里完整给出，学习时可逐行对照源页复算。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.20 习题 9.4.2

Source: textbook PDF p.294

Problem（教材题意释义）

把 PCP 限制到二字符字母表 {0,1}，证明仍不可判定。

Topic

不可判定；PCP

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.21 习题 9.4.3

Source: textbook PDF p.294

Problem（教材题意释义）

讨论单字符字母表上的 PCP 是否可判定，并给出算法。

Topic

PCP

方法导引（通用，非本题具体答案）

先明确归约方向：要证明目标问题 B 不可判定，从已知不可判定问题 A 构造可计算映射 f，使 x∈A 当且仅当 f(x)∈B。 对 TM 语义性质，优先使用 A_TM/停机问题或 Rice 定理；构造的新机器在触发已知问题的“是”实例时表现出目标性质，否则表现出明显相反的性质。 若还要分类为 RE/非 RE，则分别讨论半判定器是否能通过交错模拟、枚举见证来接受正例，并结合补语言或已知非 RE 语言排除更强类别。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.22 习题 9.4.4

Source: textbook PDF p.294

Problem（教材题意释义）

证明 Post 标记系统的可达/终止式问题不可判定，按提示把 TM 的 ID 步骤编码为串重写。

Topic

TM；不可判定

方法导引（通用，非本题具体答案）

先给出高层算法，再说明如何落实为有限控制与带操作。典型套路是多次扫描并把已处理符号做标记；多带机可把输入、工作区和计数分别放在不同带上；NTM 只把“猜一个候选”作为分支，随后仍需确定地验证。 正确性用循环不变量说明每轮扫描后哪些位置已经匹配/计数，停机性用每轮至少永久标记一个符号或严格缩小未处理区间证明。 要证明模型等价，则给出编码模拟：把多个带/多个头/二维坐标编码到一条带上，每个原机一步由有限次扫描模拟。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.23 习题 9.5.1

Source: textbook PDF p.298

Problem（教材题意释义）

证明“CFG 生成至少一个回文”的文法编码集合不可判定（从 PCP 归约）。

Topic

CFG；不可判定；PCP

方法导引（通用，非本题具体答案）

先确定每个变量的语义，再写产生式并用双向正确性证明。构造型题通常把计数相等、嵌套或分段选择交给不同变量；推导题严格区分最左推导与最右推导。 正确性证明分两部分：由产生式归纳证明每个生成串都满足目标性质（soundness）；再对任意满足性质的串按长度或结构归纳，展示如何选择第一条产生式并递归生成剩余部分（completeness）。 若要求无歧义，还要说明每个串的第一条产生式/主运算符由字符串结构唯一决定。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.24 习题 9.5.2

Source: textbook PDF p.298

Problem（教材题意释义）

证明两个 CFG 的并是否为 Σ* 不可判定，并由此推出 CFG 是否生成正则语言不可判定。

Topic

CFG；不可判定

方法导引（通用，非本题具体答案）

先确定每个变量的语义，再写产生式并用双向正确性证明。构造型题通常把计数相等、嵌套或分段选择交给不同变量；推导题严格区分最左推导与最右推导。 正确性证明分两部分：由产生式归纳证明每个生成串都满足目标性质（soundness）；再对任意满足性质的串按长度或结构归纳，展示如何选择第一条产生式并递归生成剩余部分（completeness）。 若要求无歧义，还要说明每个串的第一条产生式/主运算符由字符串结构唯一决定。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。

1.25 习题 9.5.3

Source: textbook PDF p.298

Problem（教材题意释义）

证明“CFL 的补是否仍为 CFL”不可判定，使用教材构造 L_AB 与 Ogden 技巧。

Topic

Ogden；不可判定

方法导引（通用，非本题具体答案）

使用 Ogden 引理时先把真正不能被局部泵动的那一段位置全部标记。取含至少 p 个标记位置的串。 引理保证分解 uvxyz 中 vy 至少含一个标记且 vxy 至多覆盖 p 个标记，因此 v,y 被限制在关键区域附近。 再按 v,y 的位置分类并泵 i=0 或 2，得到复制边界错位或计数关系被破坏的串，从而推出原语言不是 CFL；若题目要求证明 Ogden 引理，则从 CNF 分析树上沿含大量标记叶的路径找两个同变量节点并按树的上下文重复。

Common mistakes

  • 跳过量词、边界条件或接受方式；
  • 把“存在一种构造”误写成“任意构造都成立”；
  • 图表题未先准确抄录源数据就直接计算。