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

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

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

1.1 习题 5.1.1

Source: textbook PDF p.135

Problem（教材题意释义）

为 0n1n、i≠j 或 j≠k、非 ww 二进制串、#0=2#1 等语言设计 CFG。

Topic

CFG

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

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

Common mistakes

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

1.2 习题 5.1.2

Source: textbook PDF p.136

Problem（教材题意释义）

对给定文法 S→A1B 等，给指定三个串的最左与最右推导。

Topic

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

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

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

Common mistakes

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

1.3 习题 5.1.3

Source: textbook PDF p.136

Problem（教材题意释义）

对正则表达式做结构归纳，证明每个正则语言都是 CFL。

Topic

正则表达式

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

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

Common mistakes

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

1.4 习题 5.1.4

Source: textbook PDF p.136

Problem（教材题意释义）

证明右线性文法与正则语言等价：右线性文法→ε-NFA 与 DFA→右线性文法。

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.5 习题 5.1.5

Source: textbook PDF p.136

Problem（教材题意释义）

构造一个 CFG，其语言恰好是字母表 {0,1} 上所有合法正则表达式的文本编码。

Topic

正则表达式；CFG

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

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

Common mistakes

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

1.6 习题 5.1.6

Source: textbook PDF p.136

Problem（教材题意释义）

形式化定义一步推导 ⇒，并证明 ⇒* 与产生式反复应用的直观定义一致。

Topic

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

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

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

Common mistakes

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

1.7 习题 5.1.7

Source: textbook PDF p.136

Problem（教材题意释义）

分析文法 S→aS|Sb|a|b：证明不会生成含 ba 的串，刻画 L(G) 并证明。

Topic

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

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

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

Common mistakes

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

1.8 习题 5.1.8

Source: textbook PDF p.136

Problem（教材题意释义）

证明 S→aSbS|bSaS|ε 恰好生成 #a=#b 的所有串。

Topic

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

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

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

Common mistakes

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

1.9 习题 5.2.1

Source: textbook PDF p.144

Problem（教材题意释义）

为习题 5.1.2 的文法/字符串画语法分析树，并与最左/最右推导对应。

Topic

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

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

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

Common mistakes

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

1.10 习题 5.2.2

Source: textbook PDF p.144

Problem（教材题意释义）

无 ε 产生式文法中，长度 n 串用 m 步推导时，证明分析树节点数的教材上界。

Topic

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

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

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

Common mistakes

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

1.11 习题 5.2.3

Source: textbook PDF p.144

Problem（教材题意释义）

进一步假设无单位产生式，证明更紧的分析树节点数界。

Topic

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

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

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

Common mistakes

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

1.12 习题 5.2.4

Source: textbook PDF p.144

Problem（教材题意释义）

证明若 X1…Xk⇒*α，则各变量展开保持从左到右的顺序关系。

Topic

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

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

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

Common mistakes

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

1.13 习题 5.3.1

Source: textbook PDF p.153

Problem（教材题意释义）

证明平衡圆括号语言由 B→BB|(B)|ε 生成。

Topic

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

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

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

Common mistakes

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

1.14 习题 5.3.2

Source: textbook PDF p.153

Problem（教材题意释义）

设计同时正确匹配 () 与 [] 的 CFG。

Topic

CFG

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

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

Common mistakes

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

1.15 习题 5.3.3

Source: textbook PDF p.153

Problem（教材题意释义）

针对悬挂 else 风格文法，证明教材给出的迭代成员测试算法正确。

Topic

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

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

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

Common mistakes

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

1.16 习题 5.3.4

Source: textbook PDF p.153

Problem（教材题意释义）

扩展 HTML 文法，使其支持无序列表、表格、行、表头与数据单元格。

Topic

TM

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

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

Common mistakes

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

1.17 习题 5.3.5

Source: textbook PDF p.153

Problem（教材题意释义）

把教材图 5-16 的 DTD 转换为 CFG。

Topic

CFG

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

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

Common mistakes

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

1.18 习题 5.4.1

Source: textbook PDF p.160

Problem（教材题意释义）

对歧义文法 S→aS|aSbS|ε，用串 aab 展示两棵分析树及两种最左/最右推导。

Topic

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

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

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

Common mistakes

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

1.19 习题 5.4.2

Source: textbook PDF p.160

Problem（教材题意释义）

证明上述语言恰为每个前缀都满足 #a≥#b 的串。

Topic

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

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

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

Common mistakes

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

1.20 习题 5.4.3

Source: textbook PDF p.160

Problem（教材题意释义）

为同一语言给出无歧义 CFG。

Topic

CFG

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

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

Common mistakes

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

1.21 习题 5.4.4

Source: textbook PDF p.160

Problem（教材题意释义）

刻画该歧义文法中恰有一棵分析树的串，并给有效判定方法。

Topic

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

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

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

Common mistakes

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

1.22 习题 5.4.5

Source: textbook PDF p.160

Problem（教材题意释义）

证明 5.1.2 的文法无歧义，并为同一语言构造一个歧义文法并展示其歧义。

Topic

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

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

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

Common mistakes

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

1.23 习题 5.4.6

Source: textbook PDF p.160

Problem（教材题意释义）

判断 5.1.5 的正则表达式文法是否歧义；若歧义，重写为按优先级/结合性分层的无歧义文法。

Topic

正则表达式

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

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

Common mistakes

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

1.24 习题 5.4.7

Source: textbook PDF p.160

Problem（教材题意释义）

对表达式文法 E→E+E|EE|(E)|I 展示 x+yx 的推导/分析树并证明文法歧义。

Topic

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

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

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

Common mistakes

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