exercises – 计算理论 / 计算机科学的形式化方法

1.1 习题 4.1.1

Source: textbook PDF p.101

Problem（教材题意释义）

用泵引理证明六个计数/匹配语言非正则，包括 0ⁿ¹n、平衡括号、0ⁿ¹⁰n、n≤m 等。

Topic

泵引理

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

采用反证法。假设语言正则，令泵长度为 p；选择一个长度至少 p、并把关键计数边界放在前 p 个符号之后的串 w。对任意分解 w=xyz（|xy|≤p, |y|>0），y 被迫完全落在第一个同类符号块内。取 i=0 或 i=2 泵动 y，只改变这一块的计数而不改变后续受约束部分，从而破坏题目规定的相等、匹配、平方/素数长度等关系。因此存在一个 w 使所有合法分解都无法满足泵引理，矛盾，语言非正则。对题中的每个子语言只需相应选择 w，并指出泵后破坏的具体约束。

Common mistakes

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

1.2 习题 4.1.2

Source: textbook PDF p.101

Problem（教材题意释义）

证明平方数长度、立方数长度、2 的幂长度、ww、ww^R、位取反拼接等语言非正则。

Topic

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

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

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

Common mistakes

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

1.3 习题 4.1.3

Source: textbook PDF p.101

Problem（教材题意释义）

证明二进制素数编码语言与 gcd(i,j)=1 的 0ⁱ¹j 语言非正则。

Topic

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

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

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

Common mistakes

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

1.4 习题 4.1.4

Source: textbook PDF p.101

Problem（教材题意释义）

分析对 ∅、有限语言及若干简单语言应用泵引理时“卡住”的原因，指出量词/选串错误。

Topic

泵引理

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

采用反证法。假设语言正则，令泵长度为 p；选择一个长度至少 p、并把关键计数边界放在前 p 个符号之后的串 w。对任意分解 w=xyz（|xy|≤p, |y|>0），y 被迫完全落在第一个同类符号块内。取 i=0 或 i=2 泵动 y，只改变这一块的计数而不改变后续受约束部分，从而破坏题目规定的相等、匹配、平方/素数长度等关系。因此存在一个 w 使所有合法分解都无法满足泵引理，矛盾，语言非正则。对题中的每个子语言只需相应选择 w，并指出泵后破坏的具体约束。

Common mistakes

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

1.5 习题 4.2.1

Source: textbook PDF p.112

Problem（教材题意释义）

计算给定同态 h 的若干字符串像、语言像与逆像。

Topic

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

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

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

Common mistakes

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

1.6 习题 4.2.2

Source: textbook PDF p.112

Problem（教材题意释义）

证明正则语言对右商 L/a 封闭。

Topic

封闭

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

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

Common mistakes

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

1.7 习题 4.2.3

Source: textbook PDF p.112

Problem（教材题意释义）

证明正则语言对左商 a封闭。

Topic

封闭

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

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

Common mistakes

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

1.8 习题 4.2.4

Source: textbook PDF p.112

Problem（教材题意释义）

判断四个商运算恒等式是否总成立，并为错误命题给反例。

Topic

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

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

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

Common mistakes

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

1.9 习题 4.2.5

Source: textbook PDF p.112

Problem（教材题意释义）

推导正则语言/正则表达式的 Brzozowski 导数规则，并刻画导数为空或等于原语言的情形。

Topic

正则表达式

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

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

Common mistakes

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

1.10 习题 4.2.6

Source: textbook PDF p.112

Problem（教材题意释义）

证明正则语言对 min(L)、max(L)、init(L) 等前缀/极小操作封闭。

Topic

封闭

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

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

Common mistakes

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

1.11 习题 4.2.7

Source: textbook PDF p.114

Problem（教材题意释义）

证明交错操作 alt(L,M) 在 L,M 正则时仍给出正则语言。

Topic

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

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

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

Common mistakes

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

1.12 习题 4.2.8

Source: textbook PDF p.114

Problem（教材题意释义）

证明取偶长度串前半部分 half(L) 保持正则性。

Topic

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

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

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

Common mistakes

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

1.13 习题 4.2.9

Source: textbook PDF p.114

Problem（教材题意释义）

推广 half：按给定增长函数 f(n) 选取前缀，分析教材三个 f 的正则性。

Topic

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

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

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

Common mistakes

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

1.14 习题 4.2.10

Source: textbook PDF p.114

Problem（教材题意释义）

证明一元字母表上的任意语言 L，其 Kleene 星 L* 是正则的，并解释素数长度示例。

Topic

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

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

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

Common mistakes

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

1.15 习题 4.2.11

Source: textbook PDF p.114

Problem（教材题意释义）

证明循环移位 cycle(L) 对正则语言封闭。

Topic

封闭

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

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

Common mistakes

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

1.16 习题 4.2.12

Source: textbook PDF p.114

Problem（教材题意释义）

对递归定义的单串语言 L_n，比较普通正则表达式长度与允许交运算后的表达式长度。

Topic

正则表达式

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

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

Common mistakes

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

1.17 习题 4.2.13

Source: textbook PDF p.114

Problem（教材题意释义）

利用封闭性从 {0ⁿ¹n} 推导两个相关语言非正则。

Topic

封闭

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

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

Common mistakes

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

1.18 习题 4.2.14

Source: textbook PDF p.114

Problem（教材题意释义）

把 DFA 的积构造推广到 NFA/ε-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.19 习题 4.2.15

Source: textbook PDF p.114

Problem（教材题意释义）

用归纳法证明积 DFA 的扩展转移函数分量逐步模拟两个原 DFA。

Topic

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

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

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

Common mistakes

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

1.20 习题 4.2.16

Source: textbook PDF p.114

Problem（教材题意释义）

补全正则表达式到自动机/封闭性定理中连接与星两种归纳情形。

Topic

正则表达式；封闭

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

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

Common mistakes

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

1.21 习题 4.2.17

Source: textbook PDF p.114

Problem（教材题意释义）

补全同态与扩展转移函数兼容性的归纳证明。

Topic

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

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

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

Common mistakes

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

1.22 习题 4.3.1

Source: textbook PDF p.118

Problem（教材题意释义）

给定正则语言的自动机，设计判定语言是否无限的算法。

Topic

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

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

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

Common mistakes

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

1.23 习题 4.3.2

Source: textbook PDF p.118

Problem（教材题意释义）

设计算法判断正则语言是否至少包含 100 个串。

Topic

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

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

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

Common mistakes

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

1.24 习题 4.3.3

Source: textbook PDF p.118

Problem（教材题意释义）

判断给定正则语言 L 是否等于 Σ*。

Topic

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

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

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

Common mistakes

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

1.25 习题 4.3.4

Source: textbook PDF p.118

Problem（教材题意释义）

判断两个正则语言是否存在公共串。

Topic

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

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

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

Common mistakes

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

1.26 习题 4.3.5

Source: textbook PDF p.118

Problem（教材题意释义）

判断是否存在一个串同时不属于两个给定正则语言。

Topic

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

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

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

Common mistakes

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

1.27 习题 4.4.1

Source: textbook PDF p.124

Problem（教材题意释义）

对图 4-14 的 DFA 做状态可区分表，并构造最小等价 DFA。

Topic

最小

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

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

Common mistakes

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

1.28 习题 4.4.2

Source: textbook PDF p.124

Problem（教材题意释义）

对图 4-15 的 DFA 做状态可区分表，并构造最小等价 DFA。

Topic

最小

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

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

Common mistakes

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

1.29 习题 4.4.3

Source: textbook PDF p.125

Problem（教材题意释义）

若 n 状态 DFA 中 p,q 可区分，给出最短区分串长度的上界并证明。

Topic

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

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

用表填充算法：先标记“一终态一非终态”的状态对；随后反复检查未标记对 (p,q)，若某输入 a 使 (δ(p,a),δ(q,a)) 已被标记，则标记 (p,q)，直至固定点。未标记的状态对等价；把等价状态合并即可得到最小 DFA。最短区分串可按标记轮次反推：第 r 轮新标记的状态对存在长度至多 r 的区分串，因此可得到与状态对数量相关的上界。

Common mistakes

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

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

1.1 习题 4.1.1

1.2 习题 4.1.2

1.3 习题 4.1.3

1.4 习题 4.1.4

1.5 习题 4.2.1

1.6 习题 4.2.2

1.7 习题 4.2.3

1.8 习题 4.2.4

1.9 习题 4.2.5

1.10 习题 4.2.6

1.11 习题 4.2.7

1.12 习题 4.2.8

1.13 习题 4.2.9

1.14 习题 4.2.10

1.15 习题 4.2.11

1.16 习题 4.2.12

1.17 习题 4.2.13

1.18 习题 4.2.14

1.19 习题 4.2.15

1.20 习题 4.2.16

1.21 习题 4.2.17

1.22 习题 4.3.1

1.23 习题 4.3.2

1.24 习题 4.3.3

1.25 习题 4.3.4

1.26 习题 4.3.5

1.27 习题 4.4.1

1.28 习题 4.4.2

1.29 习题 4.4.3