CSCI3130 L08 Part 2 封闭性与判定

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L08 Part 2 封闭性与判定 · 原件 L08-上下文无关语言性质-资料包.pdf（本地课件） p.137–178 定位：区分 CFL 的正反封闭性质，并把它们用于证明和有限算法。前后：上一份 L08-P1-上下文无关泵引理.md

p.137 Outline；p.138 Positive Properties分节页。

并通过新起点选一套规则（p.139–141）

p.139 CFL对并封闭。p.140 第一文法 $S_1\to aS_1b\mid\lambda$ ，第二 $S_2\to aS_2a\mid bS_2b\mid\lambda$ ，新增 $S\to S_1\mid S_2$ 。从S第一步选择哪支，之后就按那一文法生成，所以正好是并。p.141 一般构造相同，但先把两文法的变量重命名成互不相交，避免同名变量使两套规则意外混用。

连接通过两个子树依次生成（p.142–144）

p.142 CFL对连接封闭，p.143 同样两份文法新增 $S\to S_1S_2$ ；左子树先输出第一语言的串，右子树再输出第二语言的串。p.144 一般规则依然是保留全部原规则、添加全新起点。补充演示取第一语言ab与第二语言abba，连接为ababba；这不要求连接点唯一，也不要求两个子串同长。

闭包需要零次出口（p.145–147）

p.145 声明星号封闭。p.146 对等量a后b语言加 $S_1\to SS_1\mid\lambda$ ：每次递归生成一个完整旧语言成员，最终空规则结束。p.147 第k次递归后生成k个成员，k=0直接生成空串。每个块内计数相等，整串未必所有a都在所有b前；例如ab与aabb连接为abaabb，仍属于星号语言。

p.148 Negative Properties分节页。

两个 CFL 的交可能超出 CFL（p.149–150）

p.149 “不封闭”指存在反例，不是每一对交集都非CFL。p.150 取 $L_1=\{a^nb^nc^m:n,m\ge0\}$ 、 $L_2=\{a^nb^mc^m:n,m\ge0\}$ 。第一语言可用等量a/b核心后接任意c，第二用任意a后接等量b/c核心，因此两者CFL。交集同时要求a=b、b=c，恰是已证非CFL的 $\{a^nb^nc^n\}$ 。两台PDA各有一个栈，不能照DFA乘积想当然把“两栈”仍当一栈。

p.150 的两套完整规则（变量分别属于各自文法）为：

\begin{aligned} G_1:\quad&S\to AC,&A&\to aAb\mid\lambda,&C&\to cC\mid\lambda,\\ G_2:\quad&S\to AB,&A&\to aA\mid\lambda,&B&\to bBc\mid\lambda. \end{aligned}

第一套每次 A 递归同时添一个 a、b，C 独立添 c；第二套 A 独立添 a，B 同时添 b、c。所以各自只承担一项配对，交集才要求两项同时成立。

补不封闭的反证（p.151–152）

p.151 声明补不封闭。p.152 原图的补线已视觉核对，使用的是

\overline{\overline{L_1}\cup\overline{L_2}}=L_1\cap L_2.

若CFL对补也封闭，那么两次取补加一次已知封闭的并，就使任意两CFL的交仍CFL，与上一例矛盾。这个论证说明至少某个CFL的补不是CFL，并没有单独宣称该图所列两个语言各自的补都非CFL。

p.153 与正则语言求交分节页。

一个栈配一个有限状态机（p.154–156）【新】

p.154 CFL与正则语言交仍CFL。p.155 取NPDA M1与DFA M2，使用状态对和原NPDA的唯一一个栈。p.156 若M1在读a时把顶B换C、q1→q2，同时M2读a从p1→p2，则乘积机从(q1,p1)到(q2,p2)，同样把B换C。只有第一台需要栈，故构造仍是一台NPDA。

空步不能推进 DFA（p.157–159）

p.157 NPDA若空转，DFA没有读入字符，因此它的状态保持p1。p.158 初态为两个初态组成的有序对；p.159 只有两分量都终态才是乘积终态。若把空转误当成DFA也走一步，就会使两台不再处理同一个输入前缀。

示例筛掉 b、d（p.160–162）

p.160 $L_1$ 由长度相等的两段组成，前段只含a、b，后段只含c、d；NPDA每读前段一个字符压1，每读后段一个字符弹1。p.161 $L_2=\{a,c\}^{\ast}$ ，图只显示a、c自环的接受态p0；若共同输入字母表为a、b、c、d，还应补b、d到拒绝死态，这部分图省略了。p.162 求交后只剩前段a、后段c，语言为 $\{a^nc^n:n\ge0\}$ 。补充验算aacc压两次再弹两次接受；abcc被DFA分量在b处拒绝，即使PDA计数恰好相等。

p.160–162 的图必须保留栈底测试：p.160 的最后一条边为 λ,z,z，表示只有匹配额度全部弹完才进终态。p.162 画成了 λ,λ,λ，视觉复核确实如此；若照此不检查栈顶，输入 a 也可在压入1后连走两条空边到终态，误收不等长的串。因此下表采用保留原 p.160 栈底检查的正确乘积。含 q0、q3 的状态对是终态，初态 (q0,p0)，初栈 z：

起点	输入、弹、压	终点
(q0,p0)	λ,λ,λ	(q1,p0)
(q1,p0)	a,λ,1	(q1,p0)
(q1,p0)	λ,λ,λ	(q2,p0)
(q2,p0)	c,1,λ	(q2,p0)
(q2,p0)	λ,z,z	(q3,p0)

表省略进入 DFA 拒绝死态的分支，它们不可能再接受。aacc 的稳定栈依次 z、1z、11z、1z、z；a 到结束仍为1z，最后一边不可用，所以拒绝。原图的区别及修正都留在这里，不能只写结论让读者自行猜哪条边有问题。

接受条件给出等价（p.163–164）

p.163 对任何w，乘积成功路径对应M1的一条成功路径与M2唯一成功路径，且二者读完同一输入；反过来这两条路径可逐步同步，NPDA空步时暂停DFA。p.164 因为乘积仍只用一个栈，交集仍CFL。这补上L07真包含证明所引用的封闭性事实。

p.165 应用分节页。

删除一个特定成员（p.166–168）

p.166 重申交正则封闭。

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

p.167 Prove that: $L=\{a^nb^n:n\ne100,n\ge0\}$ is context-free.

p.168 从已知CFL $\{a^nb^n:n\ge0\}$ 出发。要删除的仅一个串 $a^{100}b^{100}$ ，不用修改每层配对规则，正则筛选更直接。

单点补集作筛子（p.169–170）

p.169 单元素语言有限，所以正则；其相对于 $\{a,b\}^{\ast}$ 的补也正则。p.170 把等量语言与这个补交起来，恰好保留全部n≠100的成员。空串对应n=0仍留下；“排除100”不是“只允许n<100”。

任意次序的三字母等量（p.171–172）

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

p.171 Prove that: $L=\{w:n_a=n_b=n_c\}$ is not context-free.

p.172 反设L为CFL，交正则语言 $a^{\ast}b^{\ast}c^{\ast}$ ，便得三段等量语言，按封闭性应CFL，和Part1结论冲突。因此L非CFL。这里从较大语言抽出一个“规则次序切片”来反证，不能反过来从含一个非CFL子集就直接说大语言非CFL；交正则封闭性是必需的桥梁。

p.173 Decidable Properties分节页。

成员、空性与无限性（p.174–176）

p.174 成员问题可用CNF加CYK解决，固定文法下立方时间。p.175 空性取决于开始变量是否能最终生成某个终结串，可用L06的可终结变量不动点算法；若S能终结，至少有一成员，否则为空。不是只看文法里有没有终结符出现。

p.176 无限性先清无用、空及单位规则，再看变量依赖图中的有向环。只有经过清理后，环才代表可达且能结束、每绕一圈又增长终结输出的递归。若不清理，A→A的单位环不增长，A→aA无出口又根本不产生终结串，都不能推出无限语言。

依赖环如何生成无限多个串（p.177–178）

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

p.177 $S\to AB,\quad A\to aCb\mid a,\quad B\to bB\mid bb,\quad C\to cBS$ .

图中S→A、B，A→C，C→B、S，B自环，存在可达递归。所有变量可终结：B→bb、A→a、S→AB→abb、C→cBS→cbbabb。

p.178 具体走一圈 $S\Rightarrow AB\Rightarrow aCbB\Rightarrow acBSbB\Rightarrow^{\ast}acbbSbbb$ ，两次B各取bb，左右分别输出acbb和bbb。重复i圈后 $(acbb)^iS(bbb)^i$ ，再S→abb终结，得到 $(acbb)^iabb(bbb)^i$ ，长度7i+3。i不同长度不同，给出无限多成员，而非仅凭图上一个圆圈断言。

考试角度：（C 级通识）常见考法是选正则筛子做反证，或说明清理后的依赖环为什么既能增长又能终止。

正则筛选怎样选才不是循环证明（补充）

要从某个疑似非 CFL 的大语言 L 中抽出熟悉的困难语言 K，需要找一个独立已知正则的 R，使 $L\cap R=K$ ，并证明这个等式的两个包含方向。不能直接令 R=K：若 K 已非 CFL，它更不可能是正则，所需封闭定理便无法使用。正文任意次序等量语言取 $R=a^{\ast}b^{\ast}c^{\ast}$ ，这个 R 用 RE 明确表示，正则性独立于 L；相交只删掉乱序串，留下的三段计数仍相等，所以结果恰是 K。

若交出来的只是 K 的一个子集，还不能自动矛盾，那个子集可能有限甚至为空；若只是包含 K，也不够，包含关系本身不传递非 CFL 性。写等式而非含糊的“其中有三段等量”是这类证明的关键。与普通数值测试相同，一步里偷换了集合范围，后面每条定理可能都用错对象。

自检：CFL 与正则语言的差集仍为 CFL 吗？

先将差集改写成交与补，注意补的是哪一边。

展开推理与答案

若 L 是 CFL、R 是正则，则 $L-R=L\cap\overline R$ ；正则语言对补封闭，再用 CFL 与正则交封闭，所以仍是 CFL。这里没有使用“CFL 对补封闭”，因为被取补的是 R，不能把两个角色交换后照搬证明。

本讲核心考点

并、连接、星号的CFG构造（p.139–147，C 级）。
交与补不封闭的反例逻辑（p.149–152，C 级）。
NPDA与DFA乘积（p.154–164，C 级）。
正则筛选和判定问题（p.166–178，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：无

原件：L08-上下文无关语言性质-资料包.pdf（本地课件），PDF p.137–178。
本次独立学习修订：核对本讲178页文本，视觉复核 p.25、32、93、131–136、152、160、162、177；将树高证明放入正文，并修正乘积图漏写栈底检查的问题。