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

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

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

1.1 习题 3.1.1

Source: textbook PDF p.74

Problem（教材题意释义）

为若干二进制/三字符语言写正则表达式：同时出现 a,b；倒数第 10 位为 1；相邻 11 至多出现一次。

Topic

正则表达式

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

先把语言条件拆成有限个互斥或可并合的模式，再分别写表达式，最后用并号组合。 对计数模条件，最稳妥的方法是先构造模计数 DFA，再由 DFA→RE 转换；对“禁止某子串/倒数第 k 位/格式匹配”则围绕局部结构直接分段。 实用文本模式还应把空格、分隔符、可选前缀和大小写等写成可选分支。最后用几组正例和反例验证：每个正例至少命中一条分支，每个反例都应被某个约束排除。

Common mistakes

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

1.2 习题 3.1.2

Source: textbook PDF p.74

Problem（教材题意释义）

构造正则表达式：所有 00 都出现在所有 11 之前；以及 0 的个数是 5 的倍数。

Topic

正则表达式

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

先把语言条件拆成有限个互斥或可并合的模式，再分别写表达式，最后用并号组合。 对计数模条件，最稳妥的方法是先构造模计数 DFA，再由 DFA→RE 转换；对“禁止某子串/倒数第 k 位/格式匹配”则围绕局部结构直接分段。 实用文本模式还应把空格、分隔符、可选前缀和大小写等写成可选分支。最后用几组正例和反例验证：每个正例至少命中一条分支，每个反例都应被某个约束排除。

Common mistakes

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

1.3 习题 3.1.3

Source: textbook PDF p.74

Problem（教材题意释义）

构造正则表达式：避免子串 101；任意前缀中 0/1 数量差不超过 2；0 数为 5 的倍数且 1 数为偶数。

Topic

正则表达式

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

先把语言条件拆成有限个互斥或可并合的模式，再分别写表达式，最后用并号组合。 对计数模条件，最稳妥的方法是先构造模计数 DFA，再由 DFA→RE 转换；对“禁止某子串/倒数第 k 位/格式匹配”则围绕局部结构直接分段。 实用文本模式还应把空格、分隔符、可选前缀和大小写等写成可选分支。最后用几组正例和反例验证：每个正例至少命中一条分支，每个反例都应被某个约束排除。

Common mistakes

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

1.4 习题 3.1.4

Source: textbook PDF p.74

Problem（教材题意释义）

用自然语言描述教材给出的三个正则表达式所表示的语言。

Topic

正则表达式

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

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

Common mistakes

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

1.5 习题 3.1.5

Source: textbook PDF p.74

Problem（教材题意释义）

教材例 3.1 的闭包定义中，除空语言外指出另一个基础语言。

Topic

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

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

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

Common mistakes

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

1.6 习题 3.2.1

Source: textbook PDF p.85

Problem（教材题意释义）

对给定三状态 DFA 计算 R_ij^(k)，再用状态消除得到正则表达式，并比较消除顺序。

Topic

正则表达式；状态消除

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

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

Common mistakes

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

1.7 习题 3.2.2

Source: textbook PDF p.85

Problem（教材题意释义）

对第二个三状态 DFA 重复 R_ij^(k) / 状态消除分析。

Topic

状态消除

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

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

Common mistakes

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

1.8 习题 3.2.3

Source: textbook PDF p.85

Problem（教材题意释义）

把给定四状态 DFA 用状态消除法转换为正则表达式。

Topic

正则表达式；状态消除

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

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

Common mistakes

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

1.9 习题 3.2.4

Source: textbook PDF p.85

Problem（教材题意释义）

把 01、(0+1)01、00(0+1) 转换为 ε-NFA。

Topic

ε-NFA

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

使用本章两条标准转换链。RE→ε-NFA 时按 Thompson 构造递归处理并、连接和 Kleene 星；若要求去 ε，则先算每个状态的 ε-closure，再把读入 a 的转移定义为 closure(move(closure(S),a))。 DFA→RE 时可用 R_ij^(k) 递推或 GNFA 状态消除：消去状态 k 时把 i→j 标签更新为 R_ij + R_ik(R_kk)*R_kj。 重复直到只剩新起点和新终点，边标签即所求正则表达式；不同消除顺序可得到语法不同但语言等价的表达式。

Common mistakes

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

1.10 习题 3.2.5

Source: textbook PDF p.85

Problem（教材题意释义）

消除习题 3.2.4 所得 ε-NFA 中的 ε 转移。

Topic

ε-NFA

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

使用本章两条标准转换链。RE→ε-NFA 时按 Thompson 构造递归处理并、连接和 Kleene 星；若要求去 ε，则先算每个状态的 ε-closure，再把读入 a 的转移定义为 closure(move(closure(S),a))。 DFA→RE 时可用 R_ij^(k) 递推或 GNFA 状态消除：消去状态 k 时把 i→j 标签更新为 R_ij + R_ik(R_kk)*R_kj。 重复直到只剩新起点和新终点，边标签即所求正则表达式；不同消除顺序可得到语法不同但语言等价的表达式。

Common mistakes

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

1.11 习题 3.2.6

Source: textbook PDF p.85

Problem（教材题意释义）

分析对规范 ε-NFA 增加若干 ε 边后的语言变化，并给出构造解释。

Topic

ε-NFA

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

使用本章两条标准转换链。RE→ε-NFA 时按 Thompson 构造递归处理并、连接和 Kleene 星；若要求去 ε，则先算每个状态的 ε-closure，再把读入 a 的转移定义为 closure(move(closure(S),a))。 DFA→RE 时可用 R_ij^(k) 递推或 GNFA 状态消除：消去状态 k 时把 i→j 标签更新为 R_ij + R_ik(R_kk)*R_kj。 重复直到只剩新起点和新终点，边标签即所求正则表达式；不同消除顺序可得到语法不同但语言等价的表达式。

Common mistakes

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

1.12 习题 3.2.7

Source: textbook PDF p.86

Problem（教材题意释义）

研究 Thompson 构造的三种局部简化（并、连接、星），判断哪些简化可组合且仍保持语言正确。

Topic

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

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

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

Common mistakes

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

1.13 习题 3.2.8

Source: textbook PDF p.86

Problem（教材题意释义）

给定 DFA A 和整数 n，设计关于 n 和 |Q| 均为多项式时间的算法，计算 A 接受的长度恰为 n 的串数。

Topic

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

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

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

Common mistakes

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

1.14 习题 3.3.1

Source: textbook PDF p.90

Problem（教材题意释义）

写电话号码（含国际区号等常见格式）的实用正则表达式。

Topic

正则表达式

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

先把语言条件拆成有限个互斥或可并合的模式，再分别写表达式，最后用并号组合。 对计数模条件，最稳妥的方法是先构造模计数 DFA，再由 DFA→RE 转换；对“禁止某子串/倒数第 k 位/格式匹配”则围绕局部结构直接分段。 实用文本模式还应把空格、分隔符、可选前缀和大小写等写成可选分支。最后用几组正例和反例验证：每个正例至少命中一条分支，每个反例都应被某个约束排除。

Common mistakes

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

1.15 习题 3.3.2

Source: textbook PDF p.90

Problem（教材题意释义）

写招聘广告中薪资表达（时薪/周薪/月薪/年薪、货币符号与 K 等单位）的正则表达式。

Topic

正则表达式

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

先把语言条件拆成有限个互斥或可并合的模式，再分别写表达式，最后用并号组合。 对计数模条件，最稳妥的方法是先构造模计数 DFA，再由 DFA→RE 转换；对“禁止某子串/倒数第 k 位/格式匹配”则围绕局部结构直接分段。 实用文本模式还应把空格、分隔符、可选前缀和大小写等写成可选分支。最后用几组正例和反例验证：每个正例至少命中一条分支，每个反例都应被某个约束排除。

Common mistakes

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

1.16 习题 3.3.3

Source: textbook PDF p.90

Problem（教材题意释义）

改进教材地址匹配正则式，使其覆盖讨论中列出的遗漏情形。

Topic

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

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

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

Common mistakes

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

1.17 习题 3.4.1

Source: textbook PDF p.96

Problem（教材题意释义）

验证正则表达式代数恒等式：交换/结合/分配、星号幂等等。

Topic

正则表达式

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

证明正则表达式恒等式时不要只做字符串式代数变形，而要比较两边语言。 最直接的是双包含：任取 w 属于左侧，根据并、连接、星的语义把 w 分解，重组后证明 w 属于右侧；再反向重复。 若命题不成立，只需寻找一个最短反例串。涉及星时常用“把若干 L/M 因子视作 (L+M) 的因子序列”或反向按因子类型拆分。

Common mistakes

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

1.18 习题 3.4.2

Source: textbook PDF p.96

Problem（教材题意释义）

对教材列出的若干正则表达式等式逐个证明或给出反例。

Topic

正则表达式

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

证明正则表达式恒等式时不要只做字符串式代数变形，而要比较两边语言。 最直接的是双包含：任取 w 属于左侧，根据并、连接、星的语义把 w 分解，重组后证明 w 属于右侧；再反向重复。 若命题不成立，只需寻找一个最短反例串。涉及星时常用“把若干 L/M 因子视作 (L+M) 的因子序列”或反向按因子类型拆分。

Common mistakes

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

1.19 习题 3.4.3

Source: textbook PDF p.96

Problem（教材题意释义）

把教材例 3.6 的较长正则表达式化成两种更简单但等价的形式。

Topic

正则表达式

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

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

Common mistakes

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

1.20 习题 3.4.4

Source: textbook PDF p.96

Problem（教材题意释义）

补全 (LM)=(L+M) 一类语言代数恒等式的双包含证明。

Topic

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

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

证明正则表达式恒等式时不要只做字符串式代数变形，而要比较两边语言。 最直接的是双包含：任取 w 属于左侧，根据并、连接、星的语义把 w 分解，重组后证明 w 属于右侧；再反向重复。 若命题不成立，只需寻找一个最短反例串。涉及星时常用“把若干 L/M 因子视作 (L+M) 的因子序列”或反向按因子类型拆分。

Common mistakes

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

1.21 习题 3.4.5

Source: textbook PDF p.96

Problem（教材题意释义）

补全结构归纳证明：正则表达式为连接 FG 或闭包 F* 时，代数定律仍成立。

Topic

正则表达式

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

证明正则表达式恒等式时不要只做字符串式代数变形，而要比较两边语言。 最直接的是双包含：任取 w 属于左侧，根据并、连接、星的语义把 w 分解，重组后证明 w 属于右侧；再反向重复。 若命题不成立，只需寻找一个最短反例串。涉及星时常用“把若干 L/M 因子视作 (L+M) 的因子序列”或反向按因子类型拆分。

Common mistakes

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