CSCI3130 L11–L12 语言层级与文法 · Part 1 递归与可枚举语言

课程：CSCI3130 Formal Languages and Automata Theory 本讲：L11–L12 合讲，第 1 部分 / 共 6 部分（Outline 四部分及两段后续主题）· 原件 L11-L12-语言层级与文法-资料包.pdf（本地课件） p.1–65 定位：解释为什么有些语言能识别却不能判定，用枚举调度和对角化给出完整证明。 前后：下一份 无约束文法 承接：#L10-08 通用图灵机、#L10-09 有效枚举、#L11-01 递归可枚举、#L11-02 递归语言

同讲导航：P1 递归与可枚举语言 p.1–65；P2 无约束文法 p.66–68；P3 上下文有关语言 p.69–71；P4 乔姆斯基层级 p.72；P5 可判定性与停机问题 p.73–106；P6 归约与不可计算函数 p.107–140。

p.1 是标题页，明确是 Lecture 11 and 12；p.2 是四项 Outline，p.73 之后的可判定性和归约作为后续主题接在原顺序末尾。

语言层级里为何多了一层“递归”（p.3–5）【已会】

p.5 A language is recursively enumerable (RE) if some Turing machine accepts it

图（p.3）：按语言集合包含关系画出的嵌套区域。 元素：由内到外是 Regular、Context-free、Context-sensitive、Recursive、Recursively-enumerable；最外区域之外标 Non-recursively enumerable。 看什么：递归与递归可枚举是按图灵机的停机保证区分，不能只看机器有没有无限带。

p.4 是两类语言的分节页。p.5 的“some”是存在量词：只要找到一台识别器，便可称语言 RE，不要求任何写出来的程序都能识别。这里 recursive 是传统术语“递归语言”，不是指程序语法中用了递归调用。

成员必须接受，非成员允许不结束（p.6–8）

p.7 A language is recursive if some Turing machine accepts it and halts on any input string

p.6 对 RE 只要求成员有限步进入终态；非成员可以有限拒绝，也可以无限运行。p.7 增加对任意输入都停机的保证，p.8 因而把非成员的两种可能缩成有限拒绝。这就得到成员判定算法：每次提问都等得到是或否。

补充算例（程序自取）：识别只含 a 的语言时，“全是 a 就接受，读到 b 就一直右移”是识别器；将读到 b 的分支改成拒绝，就是判定器。前一程序会循环，不能推出该语言不递归，因为后一程序已经给出了判定器。证明语言不可判定要排除所有可能判定器。

两个枚举命题强在何处（p.9–11）

p.10 A language is recursively enumerable if and only if there is an enumeration procedure for it

p.9 是枚举分节页。p.10 先列弱结果“递归语言能枚举”，再列强结果“RE 当且仅当能枚举”。p.11 从弱结果开始：若每次成员测试都停机，就能一个接一个地测试候选串。枚举程序没有查询输入，而是不断打印语言成员；把这个输出接口与识别器的查询接口互换，需要后面两个方向的构造。

判定器作为候选串过滤器（p.12–14）

p.12 的组合框把候选生成器接到成员判定器。p.13 按长度优先列 a、b、aa、ab、ba、bb，p.14 每生成一个串就测试，接受则打印，拒绝则略过。对任一指定候选串，前面只有有限个候选，每个测试也只需有限步，所以它最终会轮到。

补充：本页例子从非空串开始。若语言定义在完整的字母表星闭包上，要把空串先列入候选，单独检查一次；这不影响后面的论证。不要把漏印空串直接推广成算法只适用于不含空串的语言。

讲义的过滤实例与新的困难（p.15–17）

表（p.15）：候选、被接受的成员和输出。

表给定的语言片段是 {b,ab,bb,aaa,…}：遇 a 不输出，遇 b 输出 b，继续到 ab 才输出第二个成员。p.16 想将结论扩大到 RE，p.17 画了相似框图。但此时内部 M 仅是识别器；图旁“Membership algorithm”的字样不能赋予它对所有输入停机的能力。p.19 正要解释这处障碍。

等待一个失败输入会阻塞整个输出（p.18–20）

p.19 Problem: If $w\notin L$ machine $M$ may loop forever

公式按讲义重排。p.18 候选仍是同一序列。p.19 若把第一个非成员交给 M 后永远等待，其后所有真成员都被卡住。p.20 改成分批推进：先运行第一个输入的一步，再引入第二个输入，分别给第二个输入第一步、第一个输入第二步。

这叫交错模拟（dovetailing）：为每个输入保存独立配置，下次轮到时从上次停止处续跑，而不是重新开始。它不要求判断当前分支是否会循环。

三角调度怎样保证不漏成员（p.21–23）

p.21 第三轮让第三个输入走第一步、第二个走第二步、第一个走第三步；p.22 用行列位置展示这种斜线调度；p.23 任一模拟进入终态，就打印对应输入。若第 i 个输入需要 t 步接受，第 i+t−1 轮就获得第 t 步，因此一定在有限时刻被发现。

算一遍（轮次为演示自取）：第二个输入需要三步，第1轮还没开始它；第2轮走第1步；第3轮走第2步；第4轮走第3步并输出。即使第一个输入永不停止，这个时刻仍然存在。完整正确性论证见附录 A1。

正文推导补全

第 r 轮引入输入 w_r，给此前尚未结束的 r 个模拟各执行一步。此时 w_i 已执行 r−i+1 步，只要 r≥i。若 w_i 是成员，其接受用时是有限 t，取 r=i+t−1 即已执行到接受步，打印它。若输出了某串，它必由识别器的一次接受触发，故不会输出非成员。每轮只处理有限个有限配置，所以轮次本身能有效完成。不要求整轮内任何一个模拟彻底结束；这排除了非成员循环导致阻塞的漏洞。

从打印程序返回查询程序（p.24–26）

p.24 If for language L there is an enumeration procedure then L is recursively enumerable

p.25 把输入 w 保留在一条带上，枚举器每正式输出一个串，就与 w 比较。p.26 一旦相同便接受；不相同继续等下一次输出。若 w 是成员，它按枚举定义会在有限时间出现；若 w 不是成员，永远不会被误接受。这正满足 RE，而不一定满足递归。

若枚举器停止输出但自己继续计算，识别器可以继续等；若枚举器彻底停机，也可拒绝。空语言的枚举器始终不输出，对应识别器始终不接受，仍符合等价命题。

数量证明之后，要找一个具体反例（p.27–29）

p.27 A language is recursively enumerable if and only if there is an enumeration procedure for it

p.27 合上两个方向；p.28 提出两个新目标：给出具体非 RE 语言，再给出 RE 但不递归语言。p.29 图把递归区域画在 RE 区域里面，外面再是非 RE 区域。L10 的计数证明只保证外面有东西，没有给出哪个串应该属于这个反例语言；下面用机器编号定义成员条件。

给机器和输入安排对应编号（p.30–32）

p.30 是非 RE 语言分节页，p.31 强调目标是没有任何图灵机能接受的语言。p.32 采用一元非空串 a,aa,aaa,…，第 i 个输入就是 a 的 i 次幂，i 从1开始。这里把语言论证的全集定为非空一元串；若要纳入空串，可独立规定空串的归属，有限个特例不会消除后面的矛盾。

编号的作用是让“第 i 台机器”遇上“第 i 个输入”。它们的编号相同不表示机器由输入生成，只是约定一个可有效恢复机器编码的序列。

接受表记录语义，不能假设整表可计算（p.33–35）

p.33 根据机器有限编码，列出 M1、M2、M3 等；p.34 把一个语言 {aa,aaaa,aaaaaa} 表成 0,1,0,1,0,1,0,…。p.35 的表如下。

1 表示存在有限接受计算；0 包括有限拒绝和无限运行。表用于数学定义，并非一张能用模拟逐格填完的电子表格：模拟一直没接受时，还不能断言最终值是0。

对角线取 1，与对角线取 0（p.36–38）

p.36 $L=\{a^i:a^i\in L(M_i)\}$

公式按讲义重排。p.36 定义正对角语言 L；p.37 表中前四个对角值为0、0、1、1，因此 aaa、aaaa 属于 L，a、aa 不属于。p.38 定义它相对于非空一元串的补语言：

补语言的位恰相反。这里必须区分 L 上方有没有横线；文本提取可能漏掉横线，本节已对照渲染页核定。只有反对角语言是马上要证明的非 RE 对象。

反设某一台机器识别了反对角语言（p.39–41）

p.39 从对角线的0读出 a、aa 属于补语言。p.40 声明补语言不是 RE。p.41 反设它是 RE，就必须存在某个索引 k，使第 k 台机器的语言等于补语言。不能只说“我们找不到这台机器”；反证法是先允许它存在，再证明这个假设与定义不相容。

用第一、第二列排除前两台候选（p.42–44）

题面（原件 · 反证中的候选检查 · p.42、44）

p.42 Question: $M_k=M_1$ ?

p.44 Question: $M_k=M_2$ ?

公式按讲义重排。p.42 问第一台是否可选，p.43 给出的区分串是 a：反对角语言含 a，而第一台在该串处是0，因此不是同一语言。p.44 换成第二台时用 aa：第二行第二列是0，所以反对角语言含 aa，第二台却不接受 aa；第二台同样排除。每次都用“机器编号对应的那一列”，而不是随便找一列。

第三台的差异方向相反，逻辑不变（p.45–47）

题面（原件 · 反证中的候选检查 · p.46）

p.46 Question: $M_k=M_3$ ?

p.45 完成第二台排除。p.46–47 检查第三台：第三行第三列为1，所以 M3 接受 aaa，而补语言不含 aaa。前两次是“补语言有、机器没有”，这次是“机器有、补语言没有”；两种情况都证明集合不相等。

对任意编号都能安排一个差异（p.48–50）

p.48 把逐个例子一般化：给任何 i，在 a 的 i 次幂上补语言与 M_i 必不同；p.49 因此不存在能够识别补语言的 M_k。p.50 的“没有算法描述”应理解为没有识别算法，不能误读成没有数学定义——p.38 已经写出了明确的集合定义。

证明的单点矛盾是：假如第 k 台识别补语言，那么它接受 a 的 k 次幂当且仅当它自己不接受该串。完整量词展开见附录 A2。

正文推导补全

设 D 为补语言，并假设 L(M_k)=D。令 x=a 的 k 次幂。若 M_k 接受 x，则 x 属于 L(M_k)，按 D 的定义 x 不属于 D；这与 L(M_k)=D 矛盾。若 M_k 不接受 x，则按定义 x 属于 D，又由 L(M_k)=D 得 M_k 必须接受 x，仍矛盾。这里“不接受”已经包含有限拒绝和循环，不需要额外决定是哪一种。两个分支穷尽所有可能，所以不存在这样一个 k。

下一目标是 RE 区域内部的不可判定对象（p.51–53）

p.51 把补语言画在 RE 外面。p.52 是 RE 但不递归分节页。p.53 右栏说机器在某些输入不停止，这只是所需现象的一部分；要证明语言不递归，还得说明无法换一台机器解决停机问题。

这次用正对角 L。定义里的“接受”是一个可以在有限运行中得到证据的事件，而“永不接受”没有这样的统一有限证据，所以两者的算法地位不同。

正对角语言的识别器要做哪些事（p.54–56）

p.54 重申 L 的定义，p.55 再显示例表中 aaa、aaaa 属于它，p.56 声明 L 是 RE。一个识别器收到一元输入后，可以数出 i，按有效机器枚举生成第 i 个合法编码，然后模拟该机器处理同一串。这些前置操作都在有限时间结束；只有最后模拟可能不停。

模拟对应机器便得到接受的充要条件（p.57–59）

p.58 If $M_i$ accepts, then accept $w$

公式按讲义重排。p.57 提出构造，p.58 列出算 i、找 M_i、模拟、接受四步。若被模拟机接受，按定义输入属于 L；若输入属于 L，该模拟必有限接受，因此新机也接受。p.59 汇总：L 为 RE，补语言非 RE。

算一遍（采用 p.35 的示意表）：输入 aaa，先数出3、取 M3、模拟 M3(aaa)，因表中相应格为1而最终接受。输入 aa 则取 M2；表中格为0只告诉它不接受，不能从表中推断它究竟有限拒绝还是死循环。

正反两侧都能识别，就能保证回答（p.60–62）

p.60 If a language L and its complement $\overline L$ are both recursively enumerable, then both languages are recursive.

公式按讲义重排。p.60 对同一输入交错模拟 L 与补语言的识别器；输入必属于其中恰一方，所以那一方最终接受。L 的识别器先接受便回答是，补语言的识别器先接受便回答否，必有有限答案。不能先等待一方完全结束，再运行另一方。

p.61 要证明正对角 L 不递归。p.62 反设 L 有判定器，则把判定器的有限接受与有限拒绝互换，便得到补语言的判定器。这一步之所以合法，关键是原程序对每个输入都停机；只给 RE 识别器不能如此取补。

p.60 原页的枚举器版本：课件图写的是枚举器 M 和补语言枚举器，而不是两个输入识别器。也可直接按原图构造：保存待查 w，交替给两个枚举器各一步，每次出现一个完整输出就与 w 比较；左边输出 w 回答属于 L，右边输出 w 回答不属于 L。任何 w 恰在一边，且该边最终会打印它，所以总能给答案。不要等“左边的下一个输出”才切换右边，因为左边可能永不再输出。识别器竞跑与此法证明同一定理，但调度对象不同。

两个严格分界最终得到证明（p.63–65）

p.63 指出补语言已知连 RE 都不是，却被假设变成递归，矛盾。p.64 得出 L 不递归。p.65 图把正对角 L 放在 RE 内、Recursive 外，把补语言放在 RE 外。

所以“可识别但不可判定”确实存在；“不可识别”也确实存在。两者都不是对某个程序运行时间太久的经验判断，而是对所有候选算法的限制。反转判定器的完整论证与 p.60 的调度细节见附录 A3。

考试角度：（A 级：期末-2022T1-资料包.pdf Q8，对应存在一个停机输入的识别器；扫描件视觉读取。）见附录 A4。

两台识别器竞跑时，只相信接受事件（补充）

设 A 识别 L，B 识别其补。输入 w 后，交替让两台各走一步；A 接受就回答“属于 L”，B 接受就回答“不属于 L”。若 A 停机拒绝，不能立即把它当作 B 的接受事件来用：虽然在 A 确实正确识别 L 的前提下这已排除成员，统一竞跑构造只需保留对方模拟，等待真正的正面见证。A 无限运行也不妨碍给 B 分配步骤。由于任意 w 恰属于一边，那一边的识别器必有限接受，故整体总停。

“至少一边最终接受”来自两个语言并为整个输入域，“不可能两边都接受”来自二者不相交。两个集合仅仅有交错识别器并不够；若它们遗漏某些输入，两台都可能永久不接受；若它们重叠，先跑到的结果也不能代表互补分类。算法的停机和正确性各自用了哪一条集合事实，需要明确指出。

本讲核心考点

• RE 保证成员有限接受，递归额外保证非成员有限拒绝（p.5–8，C 级）。
• 识别转枚举须公平交错，不能顺序等每个输入结束（p.16–23，C 级）。
• RE 恰为存在有效枚举器的语言（p.24–27，C 级）。
• 接受表的0包含不停机；反对角语言与第 i 行在第 i 列不同（p.33–50，C 级）。
• 正对角语言可识别而不可判定；它的补不可识别（p.54–65，C 级）。
• 一个语言及其补均 RE，当且仅当该语言递归（p.60–64，C 级）。

附录

A1 交错枚举的完整正确性（p.20–23）

第 r 轮引入输入 w_r，给此前尚未结束的 r 个模拟各执行一步。此时 w_i 已执行 r−i+1 步，只要 r≥i。若 w_i 是成员，其接受用时是有限 t，取 r=i+t−1 即已执行到接受步，打印它。若输出了某串，它必由识别器的一次接受触发，故不会输出非成员。每轮只处理有限个有限配置，所以轮次本身能有效完成。不要求整轮内任何一个模拟彻底结束；这排除了非成员循环导致阻塞的漏洞。

回到正文：三角调度

A2 反对角语言不可能被识别（p.38–49）

设 D 为补语言，并假设 L(M_k)=D。令 x=a 的 k 次幂。若 M_k 接受 x，则 x 属于 L(M_k)，按 D 的定义 x 不属于 D；这与 L(M_k)=D 矛盾。若 M_k 不接受 x，则按定义 x 属于 D，又由 L(M_k)=D 得 M_k 必须接受 x，仍矛盾。这里“不接受”已经包含有限拒绝和循环，不需要额外决定是哪一种。两个分支穷尽所有可能，所以不存在这样一个 k。

回到正文：任意编号上的差异

A3 补语言与总停机保证（p.60–64）

若 L、补语言各有识别器 A、B，交错执行 A(w)、B(w)。二者不会同时接受，因为集合不相交；至少一方接受，因为并集是整个输入域。故这个调度给出有限唯一判断。反过来，L 若有判定器，只需交换接受/拒绝即可判定其补，故二者当然也都是 RE。现知正对角 L 为 RE、补语言非 RE；如果 L 递归，交换判定器输出会让补语言递归进而 RE，与已证明结论冲突。因此 L 不递归。

回到正文：两个严格分界

A4 作业/往年题演练（非讲义内容）：存在一个停机输入的识别器

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

p.5 Give an algorithm to recognize the following language.

p.5 $L=\{\langle M\rangle:\text{Turing machine }M\text{ halts on some input}\}$.

把M的有限字母表上全部输入按长度再字典序列为w0,w1,…，包括λ。第r轮对前r+1个输入各模拟到至少r步，保留各自配置以交错前进；只要有一条运行停机，无论接受或拒绝，都接受机器编码。每轮有限工作，若M在wj上经过t步停机，轮数达到max(j,t)附近时必观察到；因此所有成员有限接受。若M对全部输入不停，永无见证，识别器持续运行，符合recognize而非decide的要求。

自取M在w0上循环、w1上2步后拒绝：不能先把w0跑到结束才去w1；交错方法第二个输入也获运行机会，一观察到拒绝停机就接受编码M，因为题问的是halts，不是accepts。M本身的拒绝与元算法的接受对象不同。

回到正文：存在一个停机输入的识别器

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.1–65；教材页脚 Ch 11。

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