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

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

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

1.1 习题 6.1.1

Source: textbook PDF p.170

Problem（教材题意释义）

给定两状态 PDA 的完整转移规则，从 (q,w,Z0) 出发列出 w=01、0011、010 的所有可达瞬时描述。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.2 习题 6.2.1

Source: textbook PDF p.176

Problem（教材题意释义）

设计 PDA：0n1n；任意前缀 #1≤#0；#0=#1。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.3 习题 6.2.2

Source: textbook PDF p.176

Problem（教材题意释义）

设计 PDA：a^i b^j c^k 中 i=j 或 j=k；以及 #0=2#1。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.4 习题 6.2.3

Source: textbook PDF p.176

Problem（教材题意释义）

设计 PDA：i≠j 或 j≠k；以及非 ww 的二进制串。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.5 习题 6.2.4

Source: textbook PDF p.176

Problem（教材题意释义）

若空栈 PDA 接受 L 且 ε∉L，修改为以空栈接受 L∪{ε}。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.6 习题 6.2.5

Source: textbook PDF p.177

Problem（教材题意释义）

跟踪教材给定 PDA 对 bab、abb 等输入的计算，并从栈行为刻画其语言。

Topic

PDA

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

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

Common mistakes

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

1.7 习题 6.2.6

Source: textbook PDF p.177

Problem（教材题意释义）

把 6.1.1 的 PDA 分别在终态接受与空栈接受之间转换。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.8 习题 6.2.7

Source: textbook PDF p.177

Problem（教材题意释义）

证明任意 PDA 都等价于只使用两个栈符号的 PDA（编码一般栈字母）。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.9 习题 6.2.8

Source: textbook PDF p.177

Problem（教材题意释义）

证明任意 PDA 可化为每一步使栈高度最多增加 1 的受限 PDA。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.10 习题 6.3.1

Source: textbook PDF p.183

Problem（教材题意释义）

把 CFG S→0S1|A, A→1A0|S|ε 转为以空栈接受的 PDA。

Topic

CFG；PDA

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

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

Common mistakes

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

1.11 习题 6.3.2

Source: textbook PDF p.183

Problem（教材题意释义）

把 CFG S→aAA, A→aS|bS|a 转为以空栈接受的 PDA。

Topic

CFG；PDA

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

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

Common mistakes

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

1.12 习题 6.3.3

Source: textbook PDF p.184

Problem（教材题意释义）

把教材给定 p,q 状态 PDA 转为 CFG。

Topic

CFG；PDA

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

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

Common mistakes

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

1.13 习题 6.3.4

Source: textbook PDF p.184

Problem（教材题意释义）

把习题 6.1.1 的 PDA 转为 CFG。

Topic

CFG；PDA

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

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

Common mistakes

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

1.14 习题 6.3.5

Source: textbook PDF p.184

Problem（教材题意释义）

为三个计数型 CFL 设计空栈 PDA：c 指数为 2(n+m)、i=2j 或 j=2k、n≤m≤2n。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.15 习题 6.3.6

Source: textbook PDF p.184

Problem（教材题意释义）

证明每个 PDA 都等价于一个单状态、以空栈接受的 PDA。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.16 习题 6.3.7

Source: textbook PDF p.184

Problem（教材题意释义）

根据 PDA→CFG 构造，给 s 个状态、t 个栈符号、压栈串长≤u 时 CFG 变量数/规模上界。

Topic

CFG；PDA

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

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

Common mistakes

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

1.17 习题 6.4.1

Source: textbook PDF p.187

Problem（教材题意释义）

判断例 6.2、习题 6.1.1、6.3.3 中的 PDA 是否为确定型 PDA，并指出冲突配置。

Topic

PDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.18 习题 6.4.2

Source: textbook PDF p.187

Problem（教材题意释义）

构造 DPDA：0n1m 中 n≤m；n≥m；以及 0n1m0^n。

Topic

PDA；DPDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.19 习题 6.4.3

Source: textbook PDF p.188

Problem（教材题意释义）

分三步证明终态/空栈 DPDA 与前缀无关语言之间的教材定理。

Topic

PDA；DPDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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

1.20 习题 6.4.4

Source: textbook PDF p.188

Problem（教材题意释义）

证明 {0n1n}∪{0n1{2n}} 不能由任何 DPDA 接受。

Topic

PDA；DPDA

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

先明确栈不变量：栈内容应该编码尚未匹配的输入数量或待展开的文法变量。设计转移时按输入阶段分状态，压栈阶段只增加相应标记，匹配阶段每读一个符号弹出一个标记。 终态接受与空栈接受的转换使用新的底栈标记和新起始/终止状态；CFG→PDA 让栈顶变量按产生式做 ε 展开，栈顶终结符与输入相同则匹配弹出。 PDA→CFG 则用变量 [pXq] 表示从状态 p、栈顶 X 出发最终弹出 X 并到 q 的所有输入串，并按转移组合产生式。

Common mistakes

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