CSCI3130 L07 Part 4 结尾小测

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L07 Part 4 结尾小测 · 原件 L07-下推自动机-资料包.pdf（本地课件） p.174 定位：完整解释原页两台 DPDA 的记号含义与严格边界。 前后：上一份 L07-P3-确定性与语言范围.md

严格大于和严格小于的确定构造（p.174）

题面（本讲 · Quiz · p.174；图片，视觉读取；公式按原题重排）

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

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

第一题照原页机器，初态q0非终态，F={q1,q2}。首a把z换Yz进入q1；第二a把Y换A；后续a把A换AA。于是读了n≥2个a后有n−1个A，Y仅在恰一个a时存在。q1或q2遇b且栈顶A就弹A并在q2；没有b读Y或z的边。故允许最多n−1个b，恰是m<n；一旦读b便无a边，顺序也正确。

补充验算原构造：a停q1、栈Yz，接受；ab因为顶Y无b边而拒绝；aab从Yz→Az→z，停q2接受；aabb最后b在z上无边拒绝。这里故意少存一个匹配额度，才能实现严格不等。每个输入与栈顶至多一边，且无空边竞争，所以是DPDA。

第二题原页初态q0、F={q2}。q0读a压A；首b遇A弹A转q1，q1继续b弹A。只有出现一个比a更多的b时，读b遇z才进入q2；q2在z上继续读b并保持z。还提供q0读b遇z直接到q2，处理n=0。没有任何b阶段的a边。

补充验算：abb走 $(q_0,abb,z)\vdash(q_0,bb,Az)\vdash(q_1,b,z)\vdash(q_2,\lambda,z)$，接受；ab在q1耗尽，非终态，拒绝；b直接q2接受；空串停q0拒绝。因而准确实现m≥n+1，即n<m，且所有动作唯一。

p.174 的规则集中表（后继只写唯一的状态及替换串，其他组合全部无规则）：

两份机器各自初态都是 q0、初栈都是 z；前者 $F=\{q_1,q_2\}$，后者 $F=\{q_2\}$。同名状态分属不同机器，不要把两组边并到一张图里运行。

考试角度：（C 级 通识）常见考法是把严格不等转成“保留一个余额”或“多消费一个字符”，再检查零计数和恰相等的边界。

两种严格不等为何采取不对称设计（补充）

n>m 允许读到一半就已经有余额，因此原机把 q1/q2 设为终态，并故意给 n 个 a 只存 n−1 个可用于 b 的额度。n=1 用 Y 记“已经读过首 a，但不准配任何 b”；第二个 a 将 Y 换为 A，才产生第一个额度。这不是常见“每个 a 压一个”的精确计数器，若误把第二步写成 AY，就会让 Y 永远留着且改变后续操作含义。

n<m 则要等到真正多读一个 b 才确认成功，故匹配相等的 q1 不能终态，额外 b 使机器进入 q2。自取 n=2：m=0、1 落在第一语言；m=2 两个严格条件都不满足；m=3、4 落在第二语言。等号处的共同拒绝，是检查这对构造是否意外写成非严格不等的关键。

本讲核心考点

• 少存一个匹配额度实现严格大于（p.174，C 级）。
• 多读一个b才接受实现严格小于（p.174，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：无

• 原件：L07-下推自动机-资料包.pdf（本地课件），PDF p.174。

• 本次独立学习修订：核对本讲174页文本，视觉复核 p.24、49、51、54、81、105、125、127–129、141、153、171、174；补全转移表、运行轨迹和规则族。