CSCI3130 L07 Part 1 非确定下推自动机

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L07 Part 1 非确定下推自动机 · 原件 L07-下推自动机-资料包.pdf（本地课件） p.1–91 定位：用栈记录未完成义务，通过完整执行理解接受与拒绝。 前后：下一份 L07-P2-PDA与文法等价.md

p.1 标题页；p.2 Outline。

本讲导航

1. P1 非确定下推自动机：p.1–91。
2. P2 PDA与文法等价：p.92–147。
3. P3 确定性与语言范围：p.148–173。
4. P4 结尾小测：p.174。

用栈保存未匹配的信息（p.3–5）【新】

p.3 的 $a^nb^n$ 需要确认 a 全在 b 前，并保存任意大的 a 数量；有限状态无法记录无界计数。p.4 的 PDA 在有限控制外增加栈，输入仍从左到右读。p.5 初始只有栈底符号 z。栈只允许操作顶部，因此它自然适合“最后保存的信息最先匹配”；不是可以任意按地址读取的数组。

七元组与边标签（p.6–8）【新】

p.6 定义 $M=(Q,\Sigma,\Gamma,\delta,q_0,z,F)$：状态、输入字母表、栈字母表、转移、初态、初始栈符号、终态集合。输入字母表与栈字母表可以不同；栈中还可能有底标记及变量等辅助符号。p.7 的 $\delta(q_1,u,s_1)$ 返回若干“新状态、替换栈顶的串”对；p.8 边 a,b,c 表示读 a、弹 b、以 c 替换，下面的栈内容不动。

压入字符串时谁在最上（p.9–11）

p.9 允许替换串不止一个符号。p.10 原栈 bhez（左端为顶），a,b,c 后变 chez。p.11 a,b,cdf 后变 cdfhez：c 在最上，随后 d、f，再是原先下层 h。不是 fdchez。若程序用逐符号 push 实现，应先压 f 再 d 再 c；图的串表示与实际调用顺序要分清。

三处空串各代表什么（p.12–14）

p.12 a,λ,c 表示读 a、不弹现有符号、在顶端压 c，bhez→cbhez。p.13 a,b,λ 表示读 a 后只弹 b，bhez→hez。p.14 a,λ,λ 表示只读 a，栈不变。这里第二位置为空是讲义的便捷记法，严格的 p.7 转移域要求真实栈顶，可对每种栈顶 t 展开成 a,t,ct 或 a,t,t；它不是把“空栈”当作一种栈符号。

本讲对空栈的约定（p.15–17）

p.15 a,z,λ 可以弹掉最后的 z，执行后栈空。p.16 之后需要 b 顶符号的边不能走；p.17 连 a,λ,c 这种便捷边也不能在空栈上走。讲义选用“空栈后无后续转移”的模型。故不弹栈记法只在栈本来非空时使用；其他教材若约定不同，不能混着推演。

非确定性是合法分支（p.18–20）

p.18 No transition is allowed to be followed When the stack is empty

p.18 汇总模型边界；p.19 以 a,z,b 替换底符号是可执行操作，执行后栈里仍有 b，不是空栈。p.20 同一个状态、输入、栈顶可以选择两种后继，也可以走不消费输入的空转。空转不等于不改栈，两件事由标签的不同位置决定。

一个具体的 NPDA 定义（p.21–23）

p.21 $\delta(q_1,a,b)=\{(q_2,cd),(q_3,\lambda)\}$ 从栈 bz 可读 a 后到 q2、栈 cdz，或到 q3、栈 z；两条都合法。

p.22–23 的目标为 $\{a^nb^n:n\ge0\}\cup\{a\}$，初栈0。初态读 a 可压1进计数态 q1，或直接到终态 q3 并清栈；初态空转也可接受空串。计数态每读 a 多压一个1，第一 b 转到弹栈态 q2，此后只允许 b 弹1；露出0后空转 q3。讲义问 $\delta(q_0,b,0)$，未列规则，答案是空集合，不能自行加一条。

p.22–23 的全部非空转移：$Q=\{q_0,q_1,q_2,q_3\}$，$\Sigma=\{a,b\}$，$\Gamma=\{0,1\}$，初态 q0、初栈0、$F=\{q_3\}$。表外后继均为空。

输入 a 可以选直接到 q3 的分支接受；输入 ab 应选压1的分支，随后 b 弹1，再清0接受。若输入 aa 选直接到 q3，还剩一个 a，故该分支不接受；另一路虽读完但停 q1，也不接受。

等量串的另一张图（p.24–26）

图（p.24）：q0 与 q3 均为双圈；q0 空转 q1，q1 压 a，首个 b 弹 a 转 q2，q2 继续读 b 弹 a，露出 z 后空转 q3。看什么：空串直接停 q0 接受，这个双圈不能漏；非空串则要完整通过两个阶段。

p.25 对 aaabbb 初始为 $(q_0,aaabbb,z)$。p.26 先空转 q1，不消耗字母，栈仍 z。后续每张图把当前读头和栈操作分开高亮，不能把图上的每个 Time 都理解成又读一位。

三个 a 逐一压栈（p.27–29）

p.27 读第一个 a，剩 aabbb，栈 az；p.28 读第二个 a，剩 abbb，栈 aaz；p.29 读第三个 a，剩 bbb，栈 aaaz。控制仍在 q1。栈中 a 的个数始终等于已读 a 的个数；z 不计入待匹配数量。

b 阶段逐一消账（p.30–32）

p.30 图准备从 q1 用首个 b 转 q2，p.31 展示弹后只剩 aaz；继续读第二 b 后 p.32 为 az。按完整 ID 公式 p.41，同一操作一次完成“读 b、弹 a、改状态”，不是高亮一页就多做一次弹栈。

接受不要求清空栈（p.33–35）

p.33 最后 b 弹掉最后 a，栈 z，再以空边到终态 q3。p.34 接受条件是存在一个计算：输入全部读完且末态在 F；栈最终是什么不作额外限制。p.35 aaabbb 满足两个条件。只到终态但还剩输入不算接受；栈只剩 z 但未在终态也不自动接受。

用瞬时描述避免歧义（p.36–38）【新】

p.36 总结目标语言；p.37 ID 写 $(q,u,s)$，q当前状态、u未读输入、s完整栈内容，左端栈顶。p.38 的 $(q_1,bbb,aaaz)$ 明确已经读完三个 a，却还没读任何 b。它比只写“栈高3”包含更多信息，因为状态决定是否仍准许读 a。

一步与完整执行（p.39–41）

p.39 读第一 b 得 $(q_2,bb,aaz)$；p.40 用 $\vdash$ 表示一步。p.41 全程为

读输入的步骤缩短 u，空步骤不缩短；每一步栈也恰按边标签更新。

三列一起核对，才能定位一条坏转移（补充）：把运行每行写成“状态 / 未读输入 / 栈顶在左的栈”。读字符边必须让第二列恰少首字符；空输入边第二列不动。无论哪种，第三列只允许替换最左栈符号及压入的新串，下面的尾部必须原样保留；第一列则按边的终点改变。例如 $(q,ab,Az)$ 走输入 a、栈顶 A、替换 BC 的边到 r，唯一正确结果是 $(r,b,BCz)$。写成 CBz 是压栈顺序错，写成 BC 是丢了底部，写成 ab 是没消费输入。

终态接受时最后栈内容可非空，并不表示栈检查可省略。计数 PDA 通常把“计数已满足”编码在能否到终态的转移中；若把计数未消完的状态也画成双圈，就会改变语言。接受定义是统一接口，题目特有的条件要由状态和栈规则实现。

接受语言的形式定义（p.42–44）

p.42 用 $\vdash^{\ast}$ 压缩零步或多步。p.43 定义 $L(M)=\{w:(q_0,w,z)\vdash^{\ast}(q_f,\lambda,s),q_f\in F\}$，s可任意。p.44 将 aaabbb 的计算代入，所以它是语言成员。存在量词意味着只要一个成功分支即可，不要求每种猜测成功。

从特例到计数不变量（p.45–47）

p.45 n个 a 留 n个栈记号，n个 b 恰好清回 z；p.46 顺序由 q1、q2 阶段锁定，故只接受 a先b后的等量串。p.47 问如果只要 a、b 数量相等、允许任意次序怎么办：单纯“a压、b弹”遇到先来的 b 会失败，必须能表示负余额。

用两种记号表示差额（p.48–50）

p.48 在计数态 q1：栈0表示 a过剩，1表示 b过剩。a遇0再压0，a遇1弹1；b遇1再压1，b遇0弹0；栈底 z 时分别压0或1。任何时刻不会混杂0与1，记号种类给符号、个数给绝对差额。只有露出 z 才可空转终态。

p.49–50 页上的输入为 abbaab，读第一个 a 得0z。p.51 起换成 abbbaa；已经视觉核对，以下按各页实际串说明，不能把换串当成一次运行中输入改变。

中途负余额（p.51–53）

p.51 对 abbbaa 读完 ab，0被划掉，实际栈回 z；p.52 第三个字符 b 压1，得1z；p.53 第四个字符 b 再压1，得11z。划掉格子不是仍在栈里的元素，文本抽取会丢失这个区别。

恢复平衡与猜中点（p.54–56）

p.54 第五字符 a 弹1，栈1z；p.55 展示剩余一个1；最后一个 a 再弹1，p.56 栈 z，读完输入后空转终态接受。完整 abbbaa 的余额依次1、0、−1、−2、−1、0。

两份输入各自的完整稳定栈序列（p.49–56）：这里列的是每个实际字符操作结束后的结果，动画中划掉的格不再计入栈。

每列最后都能由 q1 空转到 q2 接受；这两条独立轨迹解释了课件换串前后每个计数动作。

偶数回文需要猜切换时刻（p.57–59）

p.57 How do we know the middle of the string?

图的 q0 把读到的 a、b原样压栈，可在任意时刻空转 q1；q1 只读与栈顶相同的字母并弹掉，最后见 z 转 q2。p.58 abba 初始栈 z，p.59 读 a 后 az。猜测不消费输入，因此在正确中点切换时，左右两段长度才相同。

在正确中点切换（p.60–62）

p.60 读第二个字符 b 得 baz。p.61 猜此处是中点，空转 q1，未读仍 ba，栈仍 baz。p.62 准备以输入 b匹配顶端 b。栈的逆序性使下一位恰是左半段最后一个字符，不需要另外反转已保存串。

接受与另一输入的开始（p.63–65）

p.63 弹 b 后剩 az；p.64 再匹配 a，输入耗尽、栈 z，转终态。完整 abba 路径为压 a、压 b、空切换、弹 b、弹 a、空接受。p.65 换输入 abbb，不能复用上例结论。

同样猜中间但末位不匹配（p.66–68）

p.66–67 仍先压 a、b，栈 baz；p.68 在两位后切换。此时未读 bb，需要按栈顺序读 ba。第一位尚可匹配，后面将发生冲突。

一个失败分支还不够（p.69–71）

p.69–70 首 b 弹掉后，输入还剩 b、栈顶 a，无可用匹配边，分支拒绝。p.71 换另一个计算，继续尝试较晚切换。NPDA拒绝要排除全部分支，所以只展示刚才一条失败计算不足以完成证明。

把整串全压进去也不成功（p.72–74）

p.72 读 a 得 az，p.73 读 b 得 baz，p.74 再读 b 得 bbaz。机器仍在压栈态 q0；这些步骤合法，但合法执行不等于最后一定能接受。

输入耗尽时栈仍有待匹配字母（p.75–77）

p.75 最后 b 也压入，栈 bbbaz；p.76 这时才空切到 q1，已无输入可弹掉栈字母，无法到终态。p.77 声称所有计算均失败，完整理由是：若压 k个字母，剩余4−k个必须恰好弹 k个，所以 k=2是唯一可能；k=2的匹配又已失败。这样才覆盖没有画出的 k=0、1、3。

拒绝条件与另一个计数任务（p.78–80）

p.78 接受条件的否定是不存在“全读完且在终态”的计算；p.79 按未读完、非终态、非法越过栈底列失败情形。p.80 新目标 $\{a^nb^m:n\ge m-1\}$ 等价 m≤n+1，即允许 b最多比 a多一个，并不要求栈最终清空。

原单态示例的顺序限制（p.81–83）

p.81 单态 q0为终态，循环 a,λ,a；b,a,λ；b,z,λ。在输入已知为 a后b的条件下，它实现 m≤n+1：a存额度，b消费额度，底符号还能支付最后一个 b。p.82 aab 初始 z，p.83 首 a后 az。

核对说明：原图没有“读b后禁止a”的阶段，实际会接受 aba（az→z→az），但 aba不在 $a^{\ast}b^{\ast}$。因此它并未完整识别页上所写语言。修正需分“a阶段”和“b阶段”，b阶段没有 a边；两阶段均可为终态，弹掉 z 后到无出边终态。这个修正是补充，不冒充原图。

有剩余栈也可接受（p.84–86）

p.84 第二 a使栈 aaz；p.85 读 b后 az，输入耗尽且 q0为终态，所以接受 aab，印证接受不要求空栈。p.86 改输入 abbb，目标中 n=1、m=3，3≤2不成立，预期拒绝。

弹底后仍有输入（p.87–89）

p.87 a压入 az；p.88 第一 b弹 a回 z；p.89 第二 b弹 z，栈空。此时还剩最后 b，按照本讲空栈不再转移的约定，不能继续读它。

拒绝结尾与两道构造题（p.90–91）

p.90 因剩输入而拒绝，不是单因栈空。

题面（本讲 · Quiz · p.91；公式按讲义重排）

p.91 $L=\{wcw^R:w\in\{a,b\}^{\ast}\}$

$L=\{a^nb^mc^{n+m}:n\ge0,m\ge0\}$

第一题用 c明确标中点。压栈态读 a、b分别压原字母；读唯一 c时转匹配态、不改栈；之后只允许 a对a、b对b弹栈；露出 z且输入耗尽后接受。补充演示：abcba依次 z→az→baz，读 c保持 baz，读 b→az，读 a→z，接受。无 c无法离开第一阶段，第二个 c没有规则，故恰一个 c。

第二题分a阶段、b阶段、c阶段。读每个 a或b压一个统一记号 X；从a阶段允许首 b或首 c直接切换，从b阶段只允许 b或首 c，c阶段每读 c弹 X，不再允许 a、b；在初始状态单独接受空串，计数归零且全读完时接受。补充演示：abbccc压3个 X，再依次弹3个回 z；abcc同样压2弹2。若 n=0 或 m=0，跳过相应阶段；若 n=m=0，必须接受空串。这样同时保证三段顺序和 c数等于前两段总数。

p.91 两题的完整转移表（按题意展开）。第一题初态 p、终态 f、底符号 z，工作态 r 为匹配阶段。下式中的 t 遍历 a、b、z；未列规则均不存在：

第二题用初态 s 仅处理空串，a阶段 p、b阶段 r、c阶段 t，以及终态 f。$F=\{s,f\}$，s 空转 p 保持 z；x 遍历 X、z：

非空输入不能仅因 s 是终态就接受，仍须读完全部输入；无 a/b 就不能读首 c，因为此时顶为 z 而没有读 c 的规则。

考试角度：（C 级 通识）常见考法是逐步写 ID，分清非确定接受的存在量词，并用乱序串检查计数构造是否遗漏阶段限制。

考试角度：（A 级：HW04-2025T1-题目.pdf Q1，对应反转不等PDA。）见附录 A1。

考试角度：（A 级：HW04-2025T1-题目.pdf Q5，对应差一计数PDA。）见附录 A2。

考试角度：（A 级：期末-2022T1-资料包.pdf Q3；Final-Exam-2023T1-题目.pdf Q2；期末-2023T1-资料包.pdf Q2；Final-Exam-2024T1-题目.pdf Q1；期末-2024未核-资料包.pdf Q1，对应计数PDA的三个构造；扫描件视觉读取。）见附录 A3。

考试角度：（A 级：Final-Exam-2025T1-题目.pdf Q2(a–b)，对应正则条件也可用PDA实现；扫描件视觉读取。）见附录 A4。

考试角度：（A 级：Final-Exam-2024T1-题目.pdf Q5；期末-2024未核-资料包.pdf Q5；Final-Exam-2025T1-题目.pdf Q4，对应四段长度不等式的CFL构造；扫描件视觉读取。）见附录 A5。

本讲核心考点

• 三位置边标签与栈顶在左约定（p.6–18，C 级）。
• 终态接受及 ID（p.24–46，C 级）。
• 差额计数与回文中点猜测（p.47–79，C 级）。
• 计数条件和输入次序必须分别保证（p.80–91，C 级）。

附录

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

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

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

p.1 Find an npda on $\Sigma=\{a,b,c\}$ that accepts the language $L=\{w_1cw_2:w_1,w_2\in\{a,b\}^{\star},w_1\ne w_2^R\}$

先把c左侧逐符号压栈，c之后栈顶顺序正好是左串的反转。两串不等当且仅当某位置符号不同，或右侧较长，或右侧较短。需要恰一个c；不含c和多于一个c都拒绝。

以下给完整转移族。栈顶写在最左，底符Z；初态P，匹配态R，不等已确认态D，读完后确认左侧仍长的终态F。终态集{D,F}。记“(状态,输入,栈顶)→(新状态,替换串)”，未列者无转移。

F无后继，只有输入已经全耗尽的分支才能在F接受，因此提前猜“右侧结束”不会误收。D只读a/b、不读c，确保第二个c无法接受。R在Z且输入空时不接受，这正是两侧相等。

算一遍：abcb a去空格即abcba，左侧压出baZ，右侧ba依次弹b、a，最后R/Z，拒绝。abcbb第一个b匹配，第二个b与a不同进入D，接受。abc右侧空而栈baZ，可λ到F接受；c两侧均空，不等不成立，拒绝。abcbaa在匹配ba后多一个a，R/Z读a进D，接受。

正确性：D只在已见证字符差异或右长时进入，F只在结束时栈有剩余时接受；反之每种不相等原因都对应一条上述接受路径。

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

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

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

p.1 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无任何后继。转移族如下，未列者无动作：

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恰好对应不等式，因此既不漏收也不多收。

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

A3 作业/往年题演练（非讲义内容）：计数PDA的三个构造

题面块（期末-2022T1-资料包.pdf（本地课件） · Q3 · p.3，扫描件视觉读取）：

p.3 Give a pushdown automaton for the following language. $L=\{w\in\{a,b\}^{\star}:w\text{ has an unequal number of a's and b's}\}$.

p.3 For example, bab ∈ L and ab ∉ L.

底符Z，初态q，终态f。在q读a时，栈顶B则弹B，顶A/Z则压A；读b时，顶A则弹A，顶B/Z则压B。另从q在顶A或B时可λ到f并保留栈，f无后继；未列无动作。栈始终全是未抵消的同一种字母，长度为两计数差的绝对值。读完时非零差恰能进f；提前进f而未读完不接受。bab的栈Z→BZ→Z→BZ，接受；ab最终Z，无λ到f，拒绝。

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

p.1 Find an NPDA that accepts $L=\{a^n b^{2n}:n\geq0\}$.

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

p.1 Construct npda’s that accept the following languages on $\Sigma=\{a,b,c\}$: 1) $L=\{a^n b^{3n}:n\geq0\}$.

用同一构造分别取固定r=2与r=3：初态A、b阶段B、唯一终态F，底Z。A读a且顶X/Z时，在该栈顶前压r个X；A读b且顶X时弹一个X到B；B读b且顶X时弹一个X留B；A或B顶Z时可λ到F，F无后继。没有c转移，故2024题字母表中的c一律拒绝。A/B在顶Z时选择λ只可能在读完的路径成功。每个a留下r个债务，每个b抵消一个，B不读a强制顺序。r=2时aabbbb弹完4个X接受；aabbb余1个拒绝。r=3时abbb接受，abb余1个拒绝。λ从初态A/Z直接进F，正确处理n=0。

题面块（2024两文件 · Q1(2) · p.1）：

p.1 2) $L=\{a^n b^{n+m}c^m:n\geq0,m\geq1\}$.

初态A，转移的栈顶均在左：A读a在顶X/Z前压X；A可λ到B保持栈；B读b/X弹X；B读b/Z到C并换YZ，表示第一个额外b；C读b/Y压Y，C读c/Y弹Y到D；D读c/Y弹Y；D在Z上λ到F，F唯一终态且无后继。所有未列无动作。

前n个b正好抵消a，额外m个b压Y，m个c弹Y；只有先经过B→C的真实b、再C→D的真实c才可结束，所以m至少1。n=0,m=1时bc接受；n=2,m=1时aabbbc接受；aabb没有额外b/c而不能到F。每一阶段字符顺序与计数都被转移限制。

回到正文：计数PDA的三个构造

A4 作业/往年题演练（非讲义内容）：正则条件也可用PDA实现

题面块（Final-Exam-2025T1-题目.pdf（本地课件） · Q2 · p.2，扫描件视觉读取）：

p.2 Construct npda’s that accept the following languages on Σ = {a, b}:

p.2 (a) [10 points] $L=\{w\in\{a,b\}^{\star}:w\text{ ends with }ab\text{ and contains }aaa\}$.

p.2 (b) [10 points] $L=\{w\in\{a,b\}^{\star}:\text{the number of b's in }w\text{ is not a multiple of }3\}$

(a)无需使用栈计数，把DFA作为栈始终保留Z的NPDA。状态为(r,s)，r=0,1,2表示尚未见aaa且末尾连续a的长度，r=3表示已经见过aaa、此后永不退出；s=0,1,2表示与模式ab的最长后缀匹配长度。初态(0,0)，终态仅(3,2)。

r读a到min(r+1,3)，读b时若r=3仍3，否则0。s读a时不论原s都到1；读b时s=1则到2，否则0。每一字符同时更新两分量，形式为δ((r,s),x,Z)={((r′,s′),Z)}，未用λ。这给出全部12态的完整转移族。aaab：r最终3，s最终2，接受；aaa：r3但s1拒绝；ab：s2但r1之后归0、尚无aaa，拒绝。两个不变量一起证明正确。

(b)三态q0/q1/q2记b数模3，初q0，终态q1、q2，a不变，b循环加1，栈Z始终保留。形式δ(qi,a,Z)={(qi,Z)}，δ(qi,b,Z)={(q(i+1 mod3),Z)}。λ和纯a串的b数为0，是3倍数所以拒绝；b、bb接受，bbb拒绝。NPDA允许确定的特殊情形，不需要为了非确定名称增加猜测。

回到正文：正则条件也可用PDA实现

A5 作业/往年题演练（非讲义内容）：四段长度不等式的CFL构造

题面块（Final-Exam-2024T1-题目.pdf（本地课件） · Q5 · p.1；期末-2024未核-资料包.pdf（本地课件）同题；Final-Exam-2025T1-题目.pdf（本地课件） Q4 p.3同式，扫描件视觉读取）：

p.1 Prove that the language $L=\{a^n b^j a^k b^l:n+j\leq k+l\}$ is a context-free language.

构造NPDA按四阶段A、B、C、D读a、b、a、b，允许λ从A→B→C→D以支持零长度段。在A每读a压X，在B每读b压X；C每读a、D每读b，若顶X就弹一个，若顶Z则保持Z。仅在D且顶Z时λ到无后继终态F。初态A，初栈Z；所有阶段λ切换保持栈，所有未列字符动作为空。这是完整有限转移族。

前两段留下n+j份债务，后两段每字消一份，多出的字符不再欠债。读完四段且栈回Z恰表示后两段总长至少前两段。非确定性用于猜合法分段；题目语言按存在某个n,j,k,l表示，某串若有不同分段，只要存在一个满足不等式即可接受，不能强迫第一段取最大长度。

边界核对：abab唯一四个非空段均长1，压2弹2接受；λ可连续切换四阶段到F。纯a串可以取n=j=l=0、k为串长，因此也在语言内；这不是误收。对含多次a/b交替超出四段的串，没有一条阶段单向推进的路径能读完。存在这台NPDA，按PDA与CFG等价可知语言为CFL。

回到正文：四段长度不等式的CFL构造

来源与证据

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

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