Vince Jiang

CSCI3130 / 辅导 · 本站更新

CSCI3130 T06 · Part 3 确定计数 PDA

课程：CSCI3130 · 2025T1 本讲：第3部分 / 共5部分 · T06-2025T1.pdf（本地课件） p.7–8 定位：用栈和有限状态分担计数，给出无λ冲突的DPDA。 前后：上一份 Part 2 · 下一份 Part 4 承接：#L07-11 DPDA、#L07-03 终态接受

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

栈内余额与两个宽限状态（p.7–8）【已会】

p.7导航，p.8题面。

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

p.8 Show that the following language is deterministic. L={anbm:m≤n+2}L=\{a^n b^m:m\leq n+2\}

按非负指数约定，先读a再读b；每个a可抵消一个b，额外最多两个b用有限状态记录。初态A，b阶段B，超额1/2态E1/E2；这四态都为终态，底符Z，计数符X，不使用λ转移。

当前态与栈顶 读a 读b
A,Z (A,XZ) (E1,Z)
A,X (A,XX) (B,λ)
B,X 无转移 (B,λ)
B,Z 无转移 (E1,Z)
E1,Z 无转移 (E2,Z)
E2,Z 无转移 无转移

无转移表示该分支无法读完整串而拒绝；也可补显式陷阱态。B之后不能读a，强制段序。栈有X时表示尚未使用的a余额；栈空到底且继续读b时进入E1/E2。初态终结接受λ，a段结束时即使有余额也应接受，因为m可以小于n。

算一遍：aabbbb先压XX，前两个b弹空到Z，第三个b到E1，第四个到E2，接受；再来第五个b无动作，拒绝。bbb在n=0时第三个b被拒绝；aaba在已进入B后读a被拒绝，虽然总数关系满足也不能忽略段序。

每个状态/栈顶/输入组合只有一个动作且无λ动作，满足DPDA的两项确定性要求。不是仅因“算法看起来确定”就结束证明。

终态不是停机命令，余额也不是拒绝理由（补充）

把合法形状前缀写成 arbsa^r b^s。当 s≤r 时，栈有 r−s 个 X；当 s=r+1、r+2 时，分别处于 E1、E2 且只剩 Z。再来一个 b 没有合法转移，表示额度用完。状态 A 还允许下一字符为 a，而一旦读过 b，所有可达状态都禁止 a。因此状态负责阶段和最多两个超额，栈只负责无界余额，职责没有混在一起。

所有工作态都是终态并不表示机器读到一个前缀就停止：终态接受仍须耗尽输入。比如 aa 在 A 且有 XXZ 时应接受，因为0≤2+2；aabbbbb 则会在尚剩一个 b 时卡住，即使卡住前处于 E2 终态也不能接受。若错误地要求接受时栈只能有 Z，就会删掉全部 m<n 的合法输入。

自检：空串、b、bb、bbb 的判定分别是什么？

固定 n=0，直接与 m≤2 比较，再对照状态。

展开推理与答案

前三者接受，bbb 拒绝。配置依次可为初态 A/Z、E1/Z、E2/Z，而第三个 b 无转移。这个边界同时检查初态是否终态，以及“最多两个”有没有写成“恰好两个”。

本讲核心考点

  • 终态允许有栈余额，确定性同时检查λ冲突（p.7–8，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.7–8。

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