# 可计算性理论知识点复习大纲

> 知识主线：DFA/NFA -> 正则语言 -> CFG -> PDA -> 图灵机 -> 可判定性

## 使用说明

- 每个知识点后都标注了对应课件位置。
- PDF 课件用页码定位；PPT/PPTX 或旧版 PPT 用幻灯片范围/讲次定位。
- 后续如果提供考试重点，可直接按这些标题或位置做高亮。

## 1. 第一讲：有穷状态自动机和计算模型导引

**来源位置：** 第一讲 导引 +（有穷状态自动机）.ppt，全讲

**总结：** 有限自动机用有限状态记忆识别字符串集合，是理解形式语言和计算模型的起点。

**重要知识点：**

- DFA 的状态转移是确定的：当前状态和输入符号唯一决定后继（位置：第一讲，全讲）。
- NFA 允许多个后继或空转移，但与 DFA 识别能力等价（位置：第一讲，全讲）。
- 接受状态决定输入串是否属于该语言（位置：第一讲，全讲）。

**难点拆解：** 有限自动机不是没有记忆，而是记忆容量固定，所以能记奇偶、是否出现过某模式，却不能记任意长的配对数量。

**通俗例子：** 识别二进制串中 1 的个数是否为偶数，只需要“偶/奇”两个状态。

## 2. 第二讲：正则语言与正则表达式

**来源位置：** 第二讲.ppt，全讲

**总结：** 正则表达式和有限自动机是正则语言的两种等价表示，一个偏描述，一个偏执行。

**重要知识点：**

- 正则运算包括并、连接和 Kleene 闭包（位置：第二讲，全讲）。
- 正则表达式可转成 NFA，NFA 可转成 DFA（位置：第二讲，全讲）。
- 复习时把表达式、自动机和语言集合三者互相对应（位置：第二讲，全讲）。

**难点拆解：** 正则表达式不是程序语言里的字符串匹配技巧，而是一类形式语言的代数描述。

**通俗例子：** (a|b)*abb 表示所有以 abb 结尾的 a/b 串。

## 3. 第三讲：正则语言性质与非正则证明

**来源位置：** 第三讲.ppt，全讲

**总结：** 正则语言具有闭包性质；证明一个语言非正则时，常用泵引理暴露有限记忆无法完成的无限计数需求。

**重要知识点：**

- 正则语言对并、交、补、差等操作封闭（位置：第三讲，全讲）。
- 泵引理用于证明非正则，不能反向证明正则（位置：第三讲，全讲）。
- 选择被泵字符串时要让任意分解都会破坏语言条件（位置：第三讲，全讲）。

**难点拆解：** 泵引理证明的量词顺序很重要：你选长串，对方分解，你再选泵的次数让它矛盾。

**通俗例子：** {a^n b^n | n>=0} 要求 a 和 b 数量相等，有限自动机无法无限计数。

## 4. 第四讲：上下文无关文法和递归结构

**来源位置：** 第四讲.ppt，全讲

**总结：** 上下文无关文法用产生式表达嵌套、递归和树形结构，比正则语言更适合描述括号匹配和程序语法。

**重要知识点：**

- 非终结符、终结符、开始符号、产生式构成 CFG（位置：第四讲，全讲）。
- 推导、语法树和语言生成集合是 CFG 的三个观察角度（位置：第四讲，全讲）。
- 二义性文法可能让同一串拥有多棵语法树（位置：第四讲，全讲）。

**难点拆解：** 上下文无关不是“完全不看上下文”，而是替换某个非终结符时不看它左右邻居。

**通俗例子：** S -> (S)S | 空 可以生成配对括号串。

## 5. 第五讲：下推自动机和栈记忆

**来源位置：** 第五讲.ppt，全讲

**总结：** 下推自动机在有限控制基础上增加栈，能处理后进先出的递归结构，与上下文无关语言相对应。

**重要知识点：**

- PDA 的动作取决于当前状态、输入符号和栈顶符号（位置：第五讲，全讲）。
- 栈适合保存尚未匹配的括号、符号或递归层次（位置：第五讲，全讲）。
- CFG 与 PDA 在表达能力上等价（位置：第五讲，全讲）。

**难点拆解：** PDA 的栈只能看栈顶，不是任意访问内存，所以它强于有限自动机但仍弱于图灵机。

**通俗例子：** 读到左括号压栈，读到右括号弹栈，最后栈空说明匹配。

## 6. 第六讲：图灵机基本模型

**来源位置：** 第六讲.ppt，全讲

**总结：** 图灵机用无限纸带、读写头和有限控制抽象算法执行过程，是讨论可计算性的标准模型。

**重要知识点：**

- 纸带提供无界存储，读写头可移动并改写符号（位置：第六讲，全讲）。
- 一步转移包括读符号、写符号、移动方向和状态变化（位置：第六讲，全讲）。
- 停机并接受/拒绝是判定语言的关键（位置：第六讲，全讲）。

**难点拆解：** 图灵机不是现实机器设计图，而是抽象算法能力的边界模型。

**通俗例子：** 手工做长除法时，纸、笔、当前位置和规则就像一台图灵机。

## 7. 第七讲：图灵机变体与等价性

**来源位置：** 第七讲 .ppt，全讲

**总结：** 多带、非确定性等图灵机变体通常不改变可计算能力，只改变描述便利性或效率分析方式。

**重要知识点：**

- 多带图灵机可由单带图灵机模拟（位置：第七讲，全讲）。
- 非确定性图灵机在可识别能力上与确定性模型相关联（位置：第七讲，全讲）。
- Church-Turing 思想强调有效算法可由图灵机刻画（位置：第七讲，全讲）。

**难点拆解：** 模型变体看似更强，但若能被标准模型系统模拟，就没有突破可计算性的边界。

**通俗例子：** 多张草稿纸让计算更方便，但原则上可把内容编码到一张长纸带上。

## 8. 第八讲：可判定性和可识别性

**来源位置：** 第八讲.ppt，全讲

**总结：** 可判定语言存在总会停机并给出是/否答案的算法；可识别语言可能只在接受时保证停机。

**重要知识点：**

- 判定器必须对所有输入停机（位置：第八讲，全讲）。
- 识别器只要求属于语言的输入最终接受（位置：第八讲，全讲）。
- 可判定、可识别和不可识别之间要分清包含关系（位置：第八讲，全讲）。

**难点拆解：** “能接受正确答案”和“总能判断对错”不是一回事，这正是可识别与可判定的差别。

**通俗例子：** 有些程序若答案是是会给出证明，但答案是否时可能一直找不到反证。

## 9. 第九讲：不可判定性和归约证明

**来源位置：** 第九讲.ppt，全讲

**总结：** 不可判定性说明不存在处理所有输入的通用算法，停机问题和归约证明是课程收束重点。

**重要知识点：**

- 停机问题是经典不可判定问题（位置：第九讲，全讲）。
- 归约把已知难问题转换为目标问题，证明目标也难（位置：第九讲，全讲）。
- 证明时要说明若目标可判定，则已知不可判定问题也可判定，从而矛盾（位置：第九讲，全讲）。

**难点拆解：** 不可判定不是“现在没人会做”，而是逻辑上不存在适用于所有输入的算法。

**通俗例子：** 若有万能停机判定器，就可构造一个与它判断结果相反的程序产生自相矛盾。