CSCI3130 L07 Part 3 确定性与语言范围

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L07 Part 3 确定性与语言范围 · 原件 L07-下推自动机-资料包.pdf（本地课件） p.148–173 定位：先严格检查动作唯一性，再理解 DCFL 与 CFL 真包含的证明。前后：上一份 L07-P2-PDA与文法等价.md · 下一份 L07-P4-结尾小测.md

p.148 Outline，进入确定性下推自动机。

确定性检查的是同一配置可用的动作（p.149–151）【新】

p.149 单独一条读字符边或单独空边都可以是确定的；不是“一出现空边就非确定”。p.150 两条边即使输入相同，只要要求的栈顶不同，也不会同时可用。p.151 两条相同输入、相同栈顶却不同后继不允许；同一栈顶同时有空边和读字符边也不允许，因为在那个字符到来时有“先空转还是先读取”的竞争。

DPDA 的两个条件（p.152–154）

p.152 At all times at most one possible move

第一，每个 $\delta(q,a,B)$ 至多一个后继。第二，若 $\delta(q,\lambda,B)$ 非空，则对全部输入字符 c， $\delta(q,c,B)$ 都须为空。可以没有动作，这表示相应输入被拒绝，不要求总转移。

图（p.153）：q0为初始终态，读第一个a压a进入q1；q1继续a压栈，第一b弹a进入q2；q2读b弹a；见z用空边到q3。q2在栈顶a时读b、在z时空转，条件互斥；q0双圈接受空串。p.154 因而 $\{a^nb^n:n\ge0\}$ 是确定性上下文无关语言。

p.149–152 四组图的判定表：

同一状态的两条边	是否冲突	原因
a,b,w1 与 a,c,w2，b≠c	不冲突	同时只能有一个真实栈顶
λ,b,w1 与 λ,c,w2，b≠c	不冲突	空步也受栈顶条件限制
a,b,w1 到 q2 与 a,b,w2 到 q3	冲突	同一配置有两个后继
λ,b,w1 与 a,b,w2	冲突	下一位为 a 时两条都可执行

p.153 的机器初始 q0 和最终 q3 都是终态。首 a 的边 q0→q1 是 a,λ,a；q1 上同标签循环，q1→q2 是 b,a,λ；q2 上同标签循环，q2→q3 是 λ,z,z。只有 q0 的双圈负责空串；不能给 q1 加双圈，否则会误收还没有匹配 b 的纯 a 串。

一台机器非确定不等于语言非确定（p.155–157）

p.155 DCFL定义为存在某台DPDA接受它。p.156–157 回文机在压栈态既能继续读入又能空转猜中点，违反确定条件，所以这张图是NPDA。证明“这台机器非确定”很容易；证明“没有任何另一台DPDA能接受该语言”还需额外论证，不能混淆存在量词。

表达能力的真包含（p.158–160）

p.158 讲义声明NPDA比DPDA强。p.159 每台DPDA也是NPDA，所以DCFL包含于CFL；p.160 要证明真包含，必须给某个CFL并排除所有DPDA。NFA与DFA可以等价转换，不意味着带栈以后仍有同样结论。

两种计数要求的并（p.161–163）

p.161 选 $L=\{a^nb^n:n\ge0\}\cup\{a^nb^{2n}:n\ge0\}$ 。p.162 文法 $S\to S_1\mid S_2,S_1\to aS_1b\mid\lambda,S_2\to aS_2bb\mid\lambda$ 证明它是CFL。p.163 要证它不是DCFL。虽然两个分支各可确定识别，但DCFL并不因此对并封闭；一开始读同样的a前缀时不能无代价决定以后匹配一种还是两种b比例。

同一输入前缀的计算要兼容（p.164–166）

p.164 反设有DPDA M接受L。p.165 对固定n≥1，读完 $a^nb^n$ 应接受，继续读n个b得到 $a^nb^{2n}$ 也应接受。p.166 确定性让两个计算共用相同前缀计算；不能在读首a时为两个输入分别猜两条不同分支。该一致性才是后面拼接构造所用条件。

利用后讲的非CFL事实（p.167–169）

p.167 引用 $K=\{a^nb^nc^n:n\ge0\}$ 非CFL，说明以后用CFL泵引理证明。p.168 进一步称 $L\cup K$ 非CFL；其理由不能只是“K非CFL”，因为并上别的语言有时会变简单。补充推导：若 $L\cup K$ 为CFL，交正则语言 $a^+b^+c^+$ 后得到 $\{a^nb^nc^n:n\ge1\}$ ，仍应为CFL，与同一非CFL事实冲突。所用“CFL与正则语言交封闭”由L08证明。

p.169 因而只需从假设机器造出接受 $L\cup K$ 的NPDA，便足以矛盾；不必证明新机器也确定。

两份机器如何接（p.170–172）

p.170 复制M为M′，将读b的边改成读c，状态和栈字母一一对应。p.171 在原M的接受配置处，可空转到副本的对应状态，并原样保留栈。新机器保留原M接受，所以包含L；切到副本后只能沿原来后续b计算的对应c计算前进。

对固定n，M在完整有序输入中的接受长度只有 b数n或2n。因此从第一个接受长度n切换，能再消费n个c到第二个接受长度；从第二个接受长度2n切换，不能再读正数c后接受。得到的额外串恰 $a^nb^nc^n$ 。切换不消费输入、栈不丢失，是这段推理成立的关键。

原图表述边界：p.171称连接后为DPDA，但直接加空边可能与原读b边竞争，不自动满足p.152条件。把它称为NPDA即可修复此处证明，不改变结论：p.172只需“新语言是CFL”便与p.168矛盾。严谨实现还要把“是否已切换”编码进控制状态，禁止来回切换；M′的a边不应允许在c阶段重新输入a，可与正则三段顺序控制相乘。

结论和证明依赖（p.173）

p.173 排除假设DPDA，得到L非DCFL，因而DCFL严格小于CFL。证明使用了后讲的非CFL语言与交正则封闭性；在读完L08后应回来看这两处依赖。这里保留原证明路线，同时明确新拼接机只需要NPDA性质，避免用未核实的确定性作为前提。

考试角度：（C 级通识）常见考法是检查空边冲突，或区分“给出的PDA非确定”和“语言不存在任何DPDA”的不同证明负担。

考试角度：（A 级：HW04-2025T1-题目.pdf Q3，对应确定计数PDA。）见附录 A1。

考试角度：（A 级：Final-Exam-2023T1-题目.pdf Q5；期末-2023T1-资料包.pdf Q5；Final-Exam-2024T1-题目.pdf Q3；期末-2024未核-资料包.pdf Q3，对应严格大小关系的DPDA；扫描件视觉读取。）见附录 A2。

“输入读完了”不是自动赠送的转移条件（补充）

画 DPDA 时常有人写“若输入结束且栈里还有 X，就空转终态”。本讲转移函数只看当前状态、一个实际输入符号或空串、栈顶，未提供额外的“结束”测试。若在同一状态/栈顶上已有读字符动作，再补这条空转，就产生冲突；它不会因为文字说“只在最后走”而自动合法。要么题目明确引入结束标记并按它转移，要么如附录那样把“目前是否仍有余额”编码进控制状态或特殊栈符号，使输入自然耗尽时的终态资格已正确。

检查确定性也不能只数画出的箭头条数。一条简写边可能代表多个栈顶规则；两条输入相同的边若栈顶要求不同，可以互斥；一条空边与一条实字符边即使标签不同，若同状态同栈顶却会竞争。应把简写展开为 (状态, 栈顶) 小组，再逐个字符检查后继唯一，以及是否存在空边抢先选择。

自检：某个 CFL 的现成 NPDA 要猜中点，是否说明语言不属于 DCFL？

语言定义里的量词是存在一台机器，还是指定这一台？

展开推理与答案

这只证明现成机器非确定。要排除 DCFL，须证明任何 DPDA 都不可能识别它；可能存在另一种状态/栈编码消掉当前构造的猜测。正文后半的反证正是在承担这个更强证明责任。

本讲核心考点

相同栈顶上的空边与读入边冲突（p.149–152，C 级）。
机器确定性与语言DCFL定义（p.153–157，C 级）。
两计数语言之并的反证路线（p.161–173，C 级）。

附录

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

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

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

p.1 Show that the following language is deterministic. $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的两项确定性要求。不是仅因“算法看起来确定”就结束证明。

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

A2 作业/往年题演练（非讲义内容）：严格大小关系的DPDA

题面块（Final-Exam-2023T1-题目.pdf（本地课件） · Q5 · p.2；期末-2023T1-资料包.pdf（本地课件）同题）：

p.2 Show that $L=\{a^n b^m,n>m\}$ is a deterministic context-free language.

不能仅在结束时“猜栈非空”，因为那可能引入与读字符并存的λ边。用Y标记第一份a余额、X标记更上方余额，状态直接记录是否已耗光。初态s非终，a阶段A和b阶段B为终态，耗光态E非终，无λ边：

s读a/Z→A/YZ，其他无动作。
A读a/Y→A/XY，读a/X→A/XX。
A读b/X→B/λ，读b/Y→E/λ。
B读b/X→B/λ，读b/Y→E/λ。
E无读字符动作；B不读a。

最后一个余额Y被弹出时立即进非终态，因而A/B终态恰表示n>m；少于或等于时不能接受。aaab到B后还余XY，接受；aabb弹Y到E拒绝；λ在s拒绝。每个状态/顶/输入至多一个动作且无λ，确为DPDA。

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

p.1 Show that $L=\{a^n b^m,n<m\}$ is a deterministic context-free language.

反方向更直接：初态A，b匹配态B，额外b态F且仅F终态。A读a在X/Z前压X；A读b/X弹X到B，读b/Z到F保留Z；B读b/X弹X留B，读b/Z到F；F读b/Z保持。其余无动作，没有λ。只有真正读到超过a数的那个b才进入F；B与F不读a，确保a段在前。b接受，aabb拒绝，aabbb接受；所有转移确定。两台机器的终态判定都依赖已消费的输入信息，而非结束时非确定猜测。

回到正文：严格大小关系的DPDA

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.148–173。
本次独立学习修订：核对本讲174页文本，视觉复核 p.24、49、51、54、81、105、125、127–129、141、153、171、174；补全转移表、运行轨迹和规则族。