CSCI3130 L07 Part 2 PDA与文法等价

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L07 Part 2 PDA与文法等价 · 原件 L07-下推自动机-资料包.pdf（本地课件） p.92–147 定位：通过最左推导模拟与弹栈任务变量，建立 CFG 和 NPDA 的双向构造。前后：上一份 L07-P1-非确定下推自动机.md · 下一份 L07-P3-确定性与语言范围.md

p.92 Outline；p.93 等价性主题页。

等价需要双向模拟（p.94–96）

p.94 声明 CFG 生成的语言恰好是 NPDA 接受的语言。p.95 将 CFG 转成机器证明一个包含方向；p.96 将机器转回文法证明另一个。生成与接受是不同操作，等价指最终字符串集合相同，不是推导步数或机器状态数相同。

p.97 CFG 到 NPDA 分节页。

栈保存尚未完成的最左推导（p.98–100）【新】

p.98 M simulates leftmost derivations of G

p.98 先假设 G 已是 GNF，规则 $A\to aV_1\cdots V_k$ 变成读取 a、弹 A、压 $V_1\cdots V_k$ 。p.99 当前已生成的终结符前缀等于已消费输入，剩余变量串等于栈中从顶向下的串。下一步操作最左变量，正好就是栈顶。p.100 全部终结符生成完时只剩栈底 z；输入也应耗尽，再转终态。

两个 GNF 构造（p.101–102）

题面（本讲 · Example 7.6、7.7 · p.101–102；公式按讲义重排）

p.101 $S\to aSbb\mid a$ .

讲义先改 $S\to aSA\mid a,A\to bB,B\to b$ 。四条工作边为 a,S,SA；a,S,λ；b,A,B；b,B,λ。每次递归多一个 a并保留一个产生bb的 A，最终用 S→a收尾。补充演示 aabb：初栈 Sz，读 a变 SAz，读 a弹 S得 Az，读 b变 Bz，再读 b回 z，接受。

p.102 $S\to aA,\quad A\to aABC\mid bB\mid a,\quad B\to b,\quad C\to c$ .

逐条得到 a,S,A；a,A,ABC；b,A,B；a,A,λ；b,B,λ；c,C,λ。A有两条读 a 的选择，所以 NPDA需要非确定性。补充演示 aa：S读首 a换 A，A用终结规则读第二 a消去，栈底露出；若误选递归分支，虽该分支失败，不影响另一个分支接受。

一般 CFG 不必先转 GNF（p.103–105）

题面（本讲 · p.103；公式按讲义重排）

p.103 An example grammar: $S\to aSTb\mid b,\quad T\to Ta\mid\lambda$ .

What is the equivalent NPDA?

p.104 给最左推导 $S\Rightarrow aSTb\Rightarrow abTb\Rightarrow abTab\Rightarrow abab$ 。p.105 对每条 A→w加空边 λ,A,w，另对每个终结符 a加匹配边 a,a,λ。前者只展开预期结构、不读输入，后者才核对真实输入。初始化压 S，全部预期内容匹配完露出 z后转终态。

初始化与首次展开（p.106–108）

p.106 初态栈 z、未读 abab；p.107 压 S得 Sz；p.108 空展开 S→aSTb，栈 aSTbz，未读输入仍 abab。栈含终结符时代表未来必须核对的字符，不表示它已经读过。

字符匹配与继续展开（p.109–111）

p.109 以 a,a,λ消费首 a，实际栈变 STbz；p.110 选择 S→b，栈 bTbz；p.111 消费第二字符 b后，栈 Tbz，未读 ab。渲染图有划去和高亮过程，稳定 ID 以边执行后的结果为准，避免将划去符号继续算在栈里。

左递归规则也能模拟（p.112–114）

p.112 T→Ta，栈变 Tabz；p.113 T→空，栈变 abz；p.114 匹配下一个 a后栈 bz。虽然 T→Ta 左递归，NPDA仍能非确定地选有限次数后退出；错误地无限展开是一个不接受分支，不会阻止存在有限成功分支。

完成模拟与一般规则（p.115–117）

p.115 匹配最后 b后只剩 z，p.116 全读完且转终态，接受 abab。p.117 概括任意产生式 A→w都变 λ,A,w，任意终结符 a变 a,a,λ。一个变量有多个右侧时机器保留全部选择，否则只能识别原语言的一部分。

把 p.106–116 的运行放在一张表里：下面的栈左端为顶；动作栏说明这一行如何从上一行取得。

状态	未读输入	栈	刚做的动作
q0	abab	z	初始
q1	abab	Sz	初始化压 S
q1	abab	aSTbz	空展开 S→aSTb
q1	bab	STbz	匹配 a
q1	bab	bTbz	空展开 S→b
q1	ab	Tbz	匹配 b
q1	ab	Tabz	空展开 T→Ta
q1	ab	abz	空展开 T→λ
q1	b	bz	匹配 a
q1	λ	z	匹配 b
q2	λ	z	空转终态

课件动画的 Time 和高亮展示并非总是一页对应一条新边；上表按机器真实动作计数，因此输入始终是同一份 abab，且恰消费四次。

为什么两个方向都没有多串（p.118–120）

p.118–119 声明语言相等：若文法有最左推导，机器按相同规则展开并逐字匹配便接受；若机器接受，其空展开步骤组成一条合法最左推导，所有被弹去的终结符又与输入相同，所以输入由文法生成。p.120 得到 CFL 包含于 NPDA 语言类。空串也由一般构造处理：如果 S能推空，所有变量可空展开消去，机器不读输入便露底接受。

p.121 NPDA 到 CFG 分节页。

反向模拟为何要带状态信息（p.122–124）

p.122 目标是从任意 NPDA造同语言 CFG。p.123 已消费输入对应生成的终结符，待完成栈任务对应变量，但仅用栈符号作变量不够：同一栈符号在不同控制状态下可有不同后续。p.124 先规范机器，使其接受时清栈且只有一个终态，并把每步栈高变化限制为±1。

清栈与标准化转移（p.125–127）

p.125 从旧终态可非确定切到清栈阶段，只走空边逐个弹符号，最终到唯一新终态。这不能让未读输入消失：提前清栈且不再读输入的分支仍失败。一般机器还需新底标记保护，以免旧机器先弹空后无法进入清栈阶段。

p.126 标准边为 $q_i\xrightarrow{\sigma,B,\lambda}q_j$ 或 $q_i\xrightarrow{\sigma,B,CD}q_j$ ，每次弹一个并压零个或两个。p.127 将“不弹栈压 y”改成对栈顶 τ的替换 τ→yτ。原图写排除 z；若原边也可在底 z上执行，必须包含底符号的对应规则，否则会丢路径。这是已按原图核对后的适用条件说明。

规范化图中的适用范围（p.128–129）

p.128 图把 A→B拆成先弹 A，再读栈底 z并压 Bz，只在 A下面恰是 z时适用；一般 A下面可有别的符号。补充通用修正：用私有标记 X和私有中间态，先将 A替换为 XB（读原输入），再空弹 X，结果 B位于原下层上，两个步骤分别+1和−1，无需查看下层。

p.129 把长替换拆多步；已核对原图第二边又标 σ，若两步都读 σ就重复消费输入。补充正确原则：仅第一步消费原输入，其余全为空步。对 A→ $C_1\cdots C_k$ ，k≥3，可先压 $D_1C_k$ ，再将 $D_1$ 换 $D_2C_{k-1}$ ，持续展开，最后把末标记换 $C_1C_2$ 。例如 A→BCD，先 A→XD，再空步 X→BC，最终 BCD，栈顶顺序正确。私有态防止中间过程被别的原规则打断。

一个变量表示一次完整弹栈任务（p.130–132）【新】

p.130 等量计数例已经每步栈高±1：q0遇a时抵消1或增加0，遇b时抵消0或增加1；露 z可空弹到 qf。p.131 文法变量 $(q_iBq_j)$ 的含义是：从状态 qi、栈顶B开始，读出某串后恰弹完这个B及其上方后来压入的内容，在qj结束，并且不动原先B以下的栈。

p.132 若一步读 a就弹 B并到qj，直接加 $(q_iBq_j)\to a$ ；若输入为空则右侧为空。变量两端的状态是任务的开始与结束，不是相邻状态的随意编号。

压两个符号时拆成两个子任务（p.133–135）

p.133 边 $q_i\xrightarrow{a,B,CD}q_j$ 后，必须先弹掉C及其衍生内容，再弹D；二者之间的未知状态记 ql，最后状态记 qk。故对所有 k,l 加

(q_iBq_k)\to a(q_jCq_l)(q_lDq_k).

两任务衔接的 ql必须一致。p.134 开始变量为 $(q_0zq_f)$ ，代表从初始栈完成清栈接受。p.135 a,1,λ这条边给 $(q_01q_0)\to a$ ，输入a抵消一个b欠账记号1。

用一段具体栈尾理解三元变量（补充）：假设原栈为 BZ，转移先读 a，将 B 替成 CD，得到 CDZ。这里要完成的任务不是“从 qi 到 qk 的任意路径”，而是把新压入的 C、D 全部处理完，并最终露出原先的 Z。若 C 子任务读出 u，在 ql 结束而栈为 DZ；再由 D 子任务读出 v，在 qk 结束而栈为 Z，总输入就是 auv。若两任务之间的状态不一致，机器无法把它们真实接起来，所以规则中 ql 必须两次写同一个符号。

为什么遍历所有 ql，而不让文法提前算出它？从一条局部压栈边，看不出未来弹完 C 时的控制状态。有限状态集合使我们能把所有可能 ql 作为有限个规则分支；不可能完成的分支最终无法生成终结串，会自然失败。构造可以冗余，但不能凭直觉省掉未知的真实路径。

把全部中间状态列入选择（p.136–138）

p.136 对 b,z,1z，k、l可为q0或qf，所以每个起讫选择有两个分支，例如

(q_0zq_f)\to b(q_01q_0)(q_0zq_f)\mid b(q_01q_f)(q_fzq_f).

p.137 清栈边给 $(q_0zq_f)\to\lambda$ 。p.138 同时列出 b,1,11引起的规则。很多变量实际永远无法完成任务，因此可能无用；通用构造先全列再清理，比凭猜测删中间状态可靠。

完整规则与 abba 推导（p.139–140）

p.139 另列 a,z,0z和a,0,00的对称规则，并列基础弹栈 $(q_00q_0)\to b$ 、 $(q_01q_0)\to a$ 及清底规则。p.140 对abba：

\begin{aligned} (q_0zq_f)&\Rightarrow a(q_00q_0)(q_0zq_f)\\ &\Rightarrow ab(q_0zq_f)\\ &\Rightarrow abb(q_01q_0)(q_0zq_f)\\ &\Rightarrow abba(q_0zq_f)\Rightarrow abba. \end{aligned}

a压0、b弹0、b压1、a弹1，文法每步正好对应相同的计数任务。

p.138–139 的完整规则族：令 $X_{iBj}=(q_iBq_j)$ ，i、j为0或f，B为0、1、z。这个 X 只是三元变量的短名。四条压栈边分别产生下列规则；每式 k、l 独立遍历 {0,f}，因此每行代表4条具体规则，共16条，完整覆盖原表：

\begin{aligned} X_{0zk}&\to bX_{01l}X_{lzk},\\ X_{01k}&\to bX_{01l}X_{l1k},\\ X_{0zk}&\to aX_{00l}X_{lzk},\\ X_{00k}&\to aX_{00l}X_{l0k}. \end{aligned}

三条基础规则为 $X_{010}\to a$ 、 $X_{000}\to b$ 、 $X_{0zf}\to\lambda$ ，开始变量为 $X_{0zf}$ 。例如首行 k=0,l=f 是 $X_{0z0}\to bX_{01f}X_{fz0}$ ，k=f,l=0 是 $X_{0zf}\to bX_{010}X_{0zf}$ 。用这种有明确取值范围的规则族，既把原表所有分支保留，也不会把下标组合误读成字符串乘法。

Example 7.8 的中间态（p.141–142）

p.141 原机器首a在z上压A，继续a只保留A，读b弹A，最后清z。其语言是正数个a后一个b。为了把“保留A”的零高度步改成标准形，新增q3：读a弹A到q3，再空步在z上压Az回q0；本例 A下面确为z，所以这个特例拆法有效。p.142 基础文法规则 $(q_0Aq_3)\to a$ 、 $(q_0Aq_1)\to b$ 、 $(q_1zq_2)\to\lambda$ 。

大规则表怎样阅读（p.143–144）

p.143 对 q0读a将z换Az，终态下标 k与中间下标 l遍历q0至q3，一共16条展开选择，统一写为 $(q_0zq_k)\to a(q_0Aq_l)(q_lzq_k)$ 。p.144 对q3空步将z换Az，得到同样16条但无前导a： $(q_3zq_k)\to(q_0Aq_l)(q_lzq_k)$ 。这两页不是要求死记32条字符串，而是用同一模式保留所有可能的控制衔接。

等价性的任务不变量（p.145–147）

p.145 正式给变量语义：生成的串恰对应在不改变B以下栈内容的条件下，从qi到qj弹完B的计算。弹一步是归纳基础；压两个后可按“C首次被完全弹去的时刻”切成两个子任务，是归纳步骤。反过来每条文法规则也能拼接真实机器片段，不会造出不存在的计算。

p.146 开始变量代表从初始底符号到唯一终态的完整清栈，故生成串恰是接受串；p.147 得 NPDA语言包含于CFL，与前半方向合并成等价。

考试角度：（C 级通识）常见考法是解释三元变量的语义、根据一条压二符号边列产生式，并证明两个子任务的中间状态必须相同。

考试角度：（A 级：HW04-2025T1-题目.pdf Q2，对应文法转PDA。）见附录 A1。

考试角度：（A 级：Final-Exam-2023T1-题目.pdf Q3；期末-2023T1-资料包.pdf Q3；Final-Exam-2024T1-题目.pdf Q2；期末-2024未核-资料包.pdf Q2，对应两份文法到NPDA；扫描件视觉读取。）见附录 A2。

自检：CFG 展开 A→aB 时，是否同时读了输入 a？

先确认采用一般 CFG 模拟还是 GNF 合并规则。

展开推理与答案

一般模拟先用空输入边将 A 换成 aB，实际输入不动，随后用 a/a 匹配边才读 a；GNF 模拟可把这两步合并成读 a、A 换 B。两种构造都正确，但在同一轨迹中混用会重复消费或漏消费字符。

本讲核心考点

CFG到NPDA：展开与匹配分开（p.98–120，C 级）。
标准化转移的输入和栈顺序（p.124–129，C 级）。
三元变量与两子任务衔接（p.130–147，C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：HW04-2025T1-题目.pdf Q2

题面块（HW04-2025T1-题目.pdf（本地课件） · Q2 · PDF p.1；与该辅导原题一致）：

p.1 Construct a pda that accepts the language defined by the grammar $S\to aSbS\mid bSaS\mid\lambda$

栈顶在左。用初态q0、展开匹配态q、终态qf，初始栈Z。全部转移如下，未列无动作：

输入/栈顶	当前态→新态	替换栈顶
λ/Z	q0→q	SZ
λ/S	q→q	aSbS 或 bSaS 或 λ
a/a	q→q	λ
b/b	q→q	λ
λ/Z	q→qf	Z

读到变量就非确定选一条产生式，读到终结符就与输入头匹配并弹栈。只有读完整串并消完所有待推导符号，才可留在qf接受；若提前展开完而仍有输入，qf无读字符边，该分支失败。

算一遍：输入ab，从(q0,ab,Z)到(q,ab,SZ)，展开aSbS得到(q,ab,aSbSZ)，读a后(q,b,SbSZ)，第一个S取λ变(q,b,bSZ)，读b后(q,λ,SZ)，第二个S取λ，再到qf。输入λ可让初始S直接取λ。输入a不能让所有待匹配符号消失后又正确耗尽。

每次变量替换模拟一个最左推导步骤，每次终结符匹配核对推导的下一个字符，因此文法成功推导与PDA接受路径一一对应于相同的规则选择。文法描述全部a、b计数相等的串，但PDA正确性直接来自模拟，不需要先额外证明该语言刻画。

回到正文：HW04-2025T1-题目.pdf Q2

A2 作业/往年题演练（非讲义内容）：两份文法到NPDA

题面块（Final-Exam-2023T1-题目.pdf（本地课件） · Q3 · p.2；期末-2023T1-资料包.pdf（本地课件）同题，扫描件视觉读取）：

p.2 Find an NPDA for the following grammar: (10 pts)

p.2 $S\to aAA,\quad A\to aS\mid bS\mid a$

这是GNF，可将读首终结符与展开变量合为一步。状态q0、q、f，初栈Z：δ(q0,λ,Z)={(q,SZ)}；δ(q,a,S)={(q,AA)}；δ(q,a,A)={(q,S),(q,λ)}；δ(q,b,A)={(q,S)}；δ(q,λ,Z)={(f,Z)}；f唯一终态、无后继，其余转移空。栈顶在左。输入aaa：先S读a变AA，再两个A分别读a消掉，到Z后λ接受，对应S⇒aAA⇒aaA⇒aaa。空串不能消S而拒绝。每一步消耗的首终结符正是规则的第一个输出，变量后缀按顺序留栈，故模拟成立。

题面块（Final-Exam-2024T1-题目.pdf（本地课件） · Q2 · p.1；期末-2024未核-资料包.pdf（本地课件）同题）：

p.1 Construct an npda corresponding to the grammar:

p.1 $S\to aABB\mid aAA,\quad A\to aBB\mid b,\quad B\to bBB\mid A$ .

用一般CFG模拟，q0初始化SZ，q展开/匹配，f结束。全部λ展开为δ(q,λ,S)={(q,aABB),(q,aAA)}；δ(q,λ,A)={(q,aBB),(q,b)}；δ(q,λ,B)={(q,bBB),(q,A)}。终结符匹配δ(q,a,a)={(q,λ)}、δ(q,b,b)={(q,λ)}。初始化δ(q0,λ,Z)={(q,SZ)}，完成δ(q,λ,Z)={(f,Z)}。未列无动作，f无后继。

B→A是单位产生式，展开时不消耗输入；不能把它伪装成读A这个输入字母。例abb：S⇒aAA⇒abA⇒abb，对应栈SZ→aAAZ→AAZ（读a）→bAZ→AZ（读b）→bZ→Z（读b）→f。原推导与栈展开同步，任意接受路径都给一条合法终结推导。

回到正文：两份文法到NPDA

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

原件：L07-下推自动机-资料包.pdf（本地课件），PDF p.92–147。
本次独立学习修订：核对本讲174页文本，视觉复核 p.24、49、51、54、81、105、125、127–129、141、153、171、174；补全转移表、运行轨迹和规则族。