CSCI3130 L11–L12 语言层级与文法 · Part 4 乔姆斯基层级

课程：CSCI3130 Formal Languages and Automata Theory 本讲：合讲第 4 部分 / 共 6 部分 · 原件 L11-L12-语言层级与文法-资料包.pdf（本地课件） p.72 定位：把文法形式、机器模型和语言包含关系放回同一张图，避免混淆对象所属的层次。 前后：上一份 上下文有关语言 · 下一份 可判定性与停机问题 承接：#L11-09 Chomsky 层级

四类文法与两个额外的语言区域（p.72）【已会】

图（p.72）：The Chomsky Hierarchy。 元素：嵌套区域从 Regular 到 Context-free、Context-sensitive、Recursive、Recursively-enumerable；Non-recursively enumerable 写在最外椭圆之外。 看什么：进入更外层表示允许更强模型，但原先内层语言仍在里面；同一语言可同时属于多个区域。

前几部分给出的对应可整理如下。表是讲解性归纳，不是原页的表格。

“递归”按停机性质定义，不是乔姆斯基四型文法之外的第五型命名。图比较的是语言集合，不是具体文法的外观。上一 Part 的无约束算例生成单元素语言 {cd}，所以这门语言在最内圈，尽管那份原规则不是右线性的。

算一遍（用前文已教的见证）：两段等长语言 aⁿbⁿ 可以用栈接受，属于 CFL，却不是正则；三段等长 aⁿbⁿcⁿ 可以用 LBA 接受，却不是 CFL；Part 1 的正对角语言 L 是 RE 却不递归；它的补语言在 RE 之外。这些例子分别证明若干相邻或外部层次不能混为一类，不能用其中一个见证替代所有严格包含的证明。

补充（边界约定）：图的常见表述默认对空串的文法例外作一致处理。若一边允许空串，一边定义禁空串，应先处理这一项，而不是把约定差异当成模型能力差异。图本身也不支持“所有非 CFL 都是 CSL”；RE 外面的语言当然也是非 CFL，却不属于 CSL。

考试角度：（C 级 通识）常见考法是从一个已知类别推出可保证的外层类别、识别逆向推断错误，并为严格包含给出正确语言见证。

四个标准编号也可与图对应：Type 3 是正则文法，Type 2 是上下文无关文法，Type 1 是上下文有关文法，Type 0 是无约束文法。递归语言位于 Type 1 与 Type 0 语言类之间，但没有额外的标准 Type 编号。本页只画包含图，没有逐一证明所有相邻严格包含；上文给过的分离见证与尚未证明的层间差异应分开记。

读层级图时先写“已知什么”，再写“能推出什么”（补充）

已知语言正则，可以沿包含链推出它是 CFL、CSL、递归及 RE；已知语言不是 RE，可以逆着包含关系推出它也不是任何内层类别。已知不是正则却信息很少：它可能是两段等量的 CFL，也可能是三段等量的 CSL，甚至不可识别。不能把“走出最内圈”理解为“必落在紧邻那一圈”。

为了证明某语言恰需某一级，需要一份上界和一份下界。以 $a^nb^n$ 为例，CFG 或 PDA 构造是属于 CFL 的上界证据，正则泵引理是排除正则的下界证据。仅有前者不能说它非正则；仅有后者也不能说它是 CFL。类似地，一份复杂的无约束文法只是可识别性的上界，不证明语言必须使用那么强的模型。

本讲核心考点

• 正则、CFL、CSL、递归、RE 依次包含（p.72，C 级）。
• 四类文法与递归语言的停机定义不处于同一命名体系（p.72，C 级）。
• 文法形式复杂不保证其生成语言也需要复杂模型（p.72，C 级）。

附录

本页是前文结论的层级归纳，定义与推导分别在本讲 P1–P3 和相应较早讲次展开。

来源与证据

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

• 原件：L11-L12-语言层级与文法-资料包.pdf（本地课件），PDF p.72；页脚 Ch 11。

• 本次独立学习修订：核对合讲140页文本，视觉复核 p.38、60、70–71、83、94；补全正文证明并保留原页与补充构造的区分。