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

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

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

1.1 习题 7.1.1

Source: textbook PDF p.202

Problem（教材题意释义）

删除给定 CFG 中无用符号并给出化简后的文法。

Topic

CFG

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

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

Common mistakes

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

1.2 习题 7.1.2

Source: textbook PDF p.202

Problem（教材题意释义）

对文法 S→ASB|ε 等依次去 ε、单位、无用产生式并转 CNF。

Topic

CNF

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

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

Common mistakes

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

1.3 习题 7.1.3

Source: textbook PDF p.202

Problem（教材题意释义）

对教材第二个 CFG 重复完整化简/CNF 流程。

Topic

CFG；CNF

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

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

Common mistakes

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

1.4 习题 7.1.4

Source: textbook PDF p.202

Problem（教材题意释义）

对 S→AAA|B, A→aA|B, B→ε 重复完整化简/CNF 流程。

Topic

CNF

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

按固定顺序转换以避免重新引入已消除结构：先删除无用符号，再处理 ε 产生式（必要时保留新起始符），再消单位产生式，最后把长右部二叉化并把终结符替换成专用变量。 CNF 最终只允许 A→BC 或 A→a（以及必要时 S→ε）。GNF 则继续消除左递归并按变量顺序替换，使每条产生式以终结符开头。 每一步都说明语言保持关系；如果原语言含 ε，要单独处理 ε。

Common mistakes

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

1.5 习题 7.1.5

Source: textbook PDF p.202

Problem（教材题意释义）

对含 CDE 等产生式的 CFG 重复化简/CNF 流程。

Topic

CFG；CNF

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

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

Common mistakes

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

1.6 习题 7.1.6

Source: textbook PDF p.202

Problem（教材题意释义）

为平衡括号语言构造 CNF 文法。

Topic

CNF

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

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

Common mistakes

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

1.7 习题 7.1.7

Source: textbook PDF p.203

Problem（教材题意释义）

证明可空推导中产生式右部长度≤n、产生式数 p 时的推导长度上界。

Topic

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

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

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

Common mistakes

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

1.8 习题 7.1.8

Source: textbook PDF p.203

Problem（教材题意释义）

分析总 RHS 长度为 n 的无 ε CFG 转 CNF 后产生式数量的 O(n^2) 上界与紧例。

Topic

CFG；CNF

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

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

Common mistakes

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

1.9 习题 7.1.9

Source: textbook PDF p.203

Problem（教材题意释义）

补全教材若干文法化简算法正确性的归纳/不变量证明。

Topic

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

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

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

Common mistakes

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

1.10 习题 7.1.10

Source: textbook PDF p.203

Problem（教材题意释义）

判断是否每个不含 ε 的 CFL 都有仅 A→BCD 或 A→a 型产生式的文法。

Topic

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

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

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

Common mistakes

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

1.11 习题 7.1.11

Source: textbook PDF p.203

Problem（教材题意释义）

证明每个不含 ε 的 CFL 都有 Greibach 范式文法，按教材给出的分步构造。

Topic

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

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

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

Common mistakes

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

1.12 习题 7.1.12

Source: textbook PDF p.203

Problem（教材题意释义）

把 S→AA|0, A→SS|1 用 7.1.11 方法转 GNF。

Topic

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

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

按固定顺序转换以避免重新引入已消除结构：先删除无用符号，再处理 ε 产生式（必要时保留新起始符），再消单位产生式，最后把长右部二叉化并把终结符替换成专用变量。 CNF 最终只允许 A→BC 或 A→a（以及必要时 S→ε）。GNF 则继续消除左递归并按变量顺序替换，使每条产生式以终结符开头。 每一步都说明语言保持关系；如果原语言含 ε，要单独处理 ε。

Common mistakes

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

1.13 习题 7.2.1

Source: textbook PDF p.208

Problem（教材题意释义）

用 CFL 泵引理证明多种语言非 CFL：严格不等计数、素数长度、平方关系、ww^Rw 等。

Topic

泵引理

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

反设该语言是 CFL，取 CFL 泵长度 p，选择一个把多个相关计数块同时拉到长度 p 的串 z。 任意分解 z=uvwxy 满足 |vwx|≤p、|vx|>0，因此 v 与 x 至多影响相邻的少数几个块。 分类讨论 v,x 所在位置；泵 i=0 或 2 后，总能只改变部分计数/复制结构而让其他关联部分保持不变，破坏语言定义。故假设矛盾。 若题目含多个子语言，应对每个子语言明确写出选串和被破坏的等式/顺序关系。

Common mistakes

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

1.14 习题 7.2.2

Source: textbook PDF p.208

Problem（教材题意释义）

解释对有限语言、0n1n、回文等使用 CFL 泵引理时常见“卡住”原因。

Topic

泵引理

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

反设该语言是 CFL，取 CFL 泵长度 p，选择一个把多个相关计数块同时拉到长度 p 的串 z。 任意分解 z=uvwxy 满足 |vwx|≤p、|vx|>0，因此 v 与 x 至多影响相邻的少数几个块。 分类讨论 v,x 所在位置；泵 i=0 或 2 后，总能只改变部分计数/复制结构而让其他关联部分保持不变，破坏语言定义。故假设矛盾。 若题目含多个子语言，应对每个子语言明确写出选串和被破坏的等式/顺序关系。

Common mistakes

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

1.15 习题 7.2.3

Source: textbook PDF p.208

Problem（教材题意释义）

证明 Ogden 引理。

Topic

Ogden

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

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

Common mistakes

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

1.16 习题 7.2.4

Source: textbook PDF p.209

Problem（教材题意释义）

用 Ogden 引理简化证明 {ww} 不是 CFL。

Topic

Ogden

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

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

Common mistakes

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

1.17 习题 7.2.5

Source: textbook PDF p.209

Problem（教材题意释义）

用 Ogden 引理证明两个教材计数语言不是 CFL。

Topic

Ogden

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

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

Common mistakes

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

1.18 习题 7.3.1

Source: textbook PDF p.217

Problem（教材题意释义）

证明 CFL 对 init、右商 L/a、cycle 等操作封闭。

Topic

封闭

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

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

Common mistakes

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

1.19 习题 7.3.2

Source: textbook PDF p.217

Problem（教材题意释义）

为 L1,L2 设计 CFG，并分析其交是否为 CFL。

Topic

CFG

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

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

Common mistakes

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

1.20 习题 7.3.3

Source: textbook PDF p.217

Problem（教材题意释义）

分别给出反例，证明 CFL 对 min、max、half、alt 等操作一般不封闭。

Topic

封闭

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

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

Common mistakes

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

1.21 习题 7.3.4

Source: textbook PDF p.217

Problem（教材题意释义）

研究 shuffle：计算示例，并证明 REG×REG、CFL×REG 封闭，给 CFL×CFL 反例。

Topic

封闭

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

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

Common mistakes

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

1.22 习题 7.3.5

Source: textbook PDF p.217

Problem（教材题意释义）

研究 perm(L)：给正则语言使其置换闭包非正则/非 CFL，并证明二字符情形的正结果。

Topic

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

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

反设该语言是 CFL，取 CFL 泵长度 p，选择一个把多个相关计数块同时拉到长度 p 的串 z。 任意分解 z=uvwxy 满足 |vwx|≤p、|vx|>0，因此 v 与 x 至多影响相邻的少数几个块。 分类讨论 v,x 所在位置；泵 i=0 或 2 后，总能只改变部分计数/复制结构而让其他关联部分保持不变，破坏语言定义。故假设矛盾。 若题目含多个子语言，应对每个子语言明确写出选串和被破坏的等式/顺序关系。

Common mistakes

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

1.23 习题 7.3.6

Source: textbook PDF p.218

Problem（教材题意释义）

形式化证明 CFL 对反转封闭。

Topic

封闭

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

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

Common mistakes

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

1.24 习题 7.3.7

Source: textbook PDF p.218

Problem（教材题意释义）

补全逆同态保持 CFL 的教材证明。

Topic

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

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

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

Common mistakes

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

1.25 习题 7.4.1

Source: textbook PDF p.224

Problem（教材题意释义）

给 CFG 设计算法判断语言有限、是否至少 100 个串、某变量能否出现在句型中。

Topic

CFG

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

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

Common mistakes

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

1.26 习题 7.4.2

Source: textbook PDF p.224

Problem（教材题意释义）

用线性/固定点技术计算可出现在句型中的符号和可空变量。

Topic

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

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

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

Common mistakes

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

1.27 习题 7.4.3

Source: textbook PDF p.225

Problem（教材题意释义）

用 CYK 算法判断教材文法对 ababa、baaab、aabab 的成员性。

Topic

CYK

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

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

Common mistakes

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

1.28 习题 7.4.4

Source: textbook PDF p.225

Problem（教材题意释义）

证明 CNF 分析树中长度 n 串对应的变量节点数/总节点数公式。

Topic

CNF

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

按固定顺序转换以避免重新引入已消除结构：先删除无用符号，再处理 ε 产生式（必要时保留新起始符），再消单位产生式，最后把长右部二叉化并把终结符替换成专用变量。 CNF 最终只允许 A→BC 或 A→a（以及必要时 S→ε）。GNF 则继续消除左递归并按变量顺序替换，使每条产生式以终结符开头。 每一步都说明语言保持关系；如果原语言含 ε，要单独处理 ε。

Common mistakes

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

1.29 习题 7.4.5

Source: textbook PDF p.225

Problem（教材题意释义）

修改 CYK，使其计算不同语法分析树的数量而非仅判断存在性。

Topic

CYK

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

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

Common mistakes

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