CSCI3130 T06 · Part 5 差一计数 PDA

课程：CSCI3130 · 2025T1 本讲：第5部分 / 共5部分 · T06-2025T1.pdf（本地课件） p.11–12 定位：把差一不等式改写成可用单栈检查的未匹配余额。前后：上一份 Part 4 · 下一单元 T07 承接：#L07-01 NPDA、#L07-03 终态接受

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

先给一个a的免费额度（p.11–12）【已会】

p.11导航，p.12题面。

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

p.12 Find an npda on $\Sigma=\{a,b\}$ that accepts the following language $L=\{a^n b^m:n\leq m+1\}$

把条件写成max(n−1,0)≤m：第一个a不用配b，后续每个a压X，b逐个消去X；b更多无妨。底符Z，初态q0，a阶段A，b阶段B，唯一终态F，F无任何后继。转移族如下，未列者无动作：

当前态/栈顶	输入	新态/替换串
q0/Z	a	A/Z
q0/Z	b	B/Z
q0/Z	λ	F/Z
A/X或Z	a	A/在原栈顶前压X
A/X	b	B/λ
A/Z	b	B/Z
B/X	b	B/λ
B/Z	b	B/Z
A/Z或B/Z	λ	F/Z

A与B在Z上的λ转移和读字符转移并存，故这是合法NPDA，不冒称此表为DPDA。只有所有输入已读完的F路径算接受。B不读a，保证顺序。

算一遍：aaab先免费读a，再压两个X，一个b只能弹一个，输入耗尽仍X，不能到F，拒绝，因为3>1+1。aaabb弹完两个X到Z，可λ到F接受；a免费读完后在A/Z也接受；λ从q0直接到F。bbb全部在B/Z读完后接受。

不变量是栈X数为尚待b抵消的“除首a外的a数”；最终为0恰好对应不等式，因此既不漏收也不多收。

同样叫“计数”，不等式方向决定多余字符怎么办（补充）

对合法形状前缀 $a^r b^s$ ，本构造的栈高度为 $\max(r-1-s,0)$ 。在 a 阶段先给一次免费额度，所以 r=0 与 r=1 都无需 X；后续 a 才增加债务。b 抵消 X，债务归零后仍可继续读 b，因此用“截断到0”的余额而不是允许负高度。读完整串后余额为0，恰等价于 r≤s+1。

这和 Part 3 的方向相反：那里 b 太多会违规，这里 b 越多越有助于满足计数，但两题都禁止 b 后再出现 a。自取 ba 虽有 n=m=1、满足不等式，仍不属于 $a^*b^*$ ，故 B 上不能给 a 边。构造检查必须同时看数量与段序，不能只用一个数值公式代替整个语言定义。

自检：本表有 λ 分支，所以这个语言一定不是 DCFL 吗？

区分某台机器的确定性与语言是否存在确定机器。

展开推理与答案

不能这样推出。该表在 A/Z 或 B/Z 有 λ 与读字符动作竞争，所以这台机器是 NPDA；语言是否确定，需要另找 DPDA 或证明不存在，不能从一次非确定构造直接判定语言下界。

本讲核心考点

免费额度与栈余额对应n≤m+1，b阶段不再读a（p.11–12，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.11–12。
本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。原件12页只有题面与导航，解法明确标为补充。