CSCI3130 T06 · Part 2 文法转 PDA

课程：CSCI3130 · 2025T1 本讲：第2部分 / 共5部分 · T06-2025T1.pdf（本地课件） p.5–6 定位：让栈逐步模拟文法推导，明确空串与终态接受。 前后：上一份 Part 1 · 下一份 Part 3 承接：#L07-08 一般CFG转NPDA

本辅导原件只给本题题面，下面的完整转移、推导或反证为学习补充；它们不是原页印出的参考答案。读栈配置时统一把栈顶写在最左，λ边不消耗输入。

栈保存尚未匹配的句型（p.5–6）【已会】

p.5导航，p.6原题没有附解答，以下为按课程构造法补全。

题面块（T06 · Problem 2 · PDF p.6；公式按讲义重排）：

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

栈顶在左。用初态q0、展开匹配态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正确性直接来自模拟，不需要先额外证明该语言刻画。

连接“已经读过的前缀”与“栈里待做的事”（补充）

设输入为 $ur$，机器已经消耗 u，尚余 r，栈为 $\alpha Z$。对这份模拟构造，沿每条尚未失败的推导分支都有 $S\Rightarrow^*u\alpha$：读变量时按规则替换栈顶，正好替换该句型里最左侧未完成变量；读终结符时只在它等于输入头时弹出，等于把已确定的字符从 α 移入 u。若最终 α 为空且 r 也为空，就得到了 $S\Rightarrow^*u$，因此接受串确实由文法生成。

逆向则从任意最左推导出发，依次采用同样的 λ 展开，并在终结符来到栈顶时匹配输入。虽然一些其他选择会卡住，甚至可以不断展开而不结束，但只要存在这条有限成功分支就足以接受。不能因此把 NPDA 当成“所有分支都要结束”的算法；本题证明的是识别语言相同。

本讲核心考点

• 变量展开走λ边，终结符匹配才消耗输入（p.5–6，C 级）。

附录

这是辅导原题的完整演练；原件无解答页，正文构造按对应讲次的方法推导，未读取手写作答。

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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：无

• 原件：T06-2025T1.pdf（本地课件），PDF p.5–6。

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。原件12页只有题面与导航，解法明确标为补充。