# 可计算性理论考前总复习

> 脱离课件复习版：把知识脉络、必背抓手、便携记忆点和自测题放在一起，考前可以只看这一份。

## 1. 知识脉络

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

1. **第一讲：有穷状态自动机和计算模型导引**
   - 核心：有限自动机用有限状态记忆识别字符串集合，是理解形式语言和计算模型的起点。
   - 对应位置：第一讲 导引 +（有穷状态自动机）.ppt，全讲
2. **第二讲：正则语言与正则表达式**
   - 核心：正则表达式和有限自动机是正则语言的两种等价表示，一个偏描述，一个偏执行。
   - 对应位置：第二讲.ppt，全讲
3. **第三讲：正则语言性质与非正则证明**
   - 核心：正则语言具有闭包性质；证明一个语言非正则时，常用泵引理暴露有限记忆无法完成的无限计数需求。
   - 对应位置：第三讲.ppt，全讲
4. **第四讲：上下文无关文法和递归结构**
   - 核心：上下文无关文法用产生式表达嵌套、递归和树形结构，比正则语言更适合描述括号匹配和程序语法。
   - 对应位置：第四讲.ppt，全讲
5. **第五讲：下推自动机和栈记忆**
   - 核心：下推自动机在有限控制基础上增加栈，能处理后进先出的递归结构，与上下文无关语言相对应。
   - 对应位置：第五讲.ppt，全讲
6. **第六讲：图灵机基本模型**
   - 核心：图灵机用无限纸带、读写头和有限控制抽象算法执行过程，是讨论可计算性的标准模型。
   - 对应位置：第六讲.ppt，全讲
7. **第七讲：图灵机变体与等价性**
   - 核心：多带、非确定性等图灵机变体通常不改变可计算能力，只改变描述便利性或效率分析方式。
   - 对应位置：第七讲 .ppt，全讲
8. **第八讲：可判定性和可识别性**
   - 核心：可判定语言存在总会停机并给出是/否答案的算法；可识别语言可能只在接受时保证停机。
   - 对应位置：第八讲.ppt，全讲
9. **第九讲：不可判定性和归约证明**
   - 核心：不可判定性说明不存在处理所有输入的通用算法，停机问题和归约证明是课程收束重点。
   - 对应位置：第九讲.ppt，全讲

## 2. 必背抓手

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

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

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

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

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

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

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

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

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

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

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

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

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

- 多带图灵机可由单带图灵机模拟。
- 非确定性图灵机在可识别能力上与确定性模型相关联。
- Church-Turing 思想强调有效算法可由图灵机刻画。

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

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

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

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

## 3. 便携记忆点

- **第一讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第一讲 导引 +（有穷状态自动机）.ppt`，用一句话背：有限自动机用有限状态记忆识别字符串集合，是理解形式语言和计算模型的起点。
- **第二讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第二讲.ppt`，用一句话背：正则表达式和有限自动机是正则语言的两种等价表示，一个偏描述，一个偏执行。
- **第三讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第三讲.ppt`，用一句话背：正则语言具有闭包性质；证明一个语言非正则时，常用泵引理暴露有限记忆无法完成的无限计数需求。
- **第四讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第四讲.ppt`，用一句话背：上下文无关文法用产生式表达嵌套、递归和树形结构，比正则语言更适合描述括号匹配和程序语法。
- **第五讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第五讲.ppt`，用一句话背：下推自动机在有限控制基础上增加栈，能处理后进先出的递归结构，与上下文无关语言相对应。
- **第六讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第六讲.ppt`，用一句话背：图灵机用无限纸带、读写头和有限控制抽象算法执行过程，是讨论可计算性的标准模型。
- **第七讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第七讲 .ppt`，用一句话背：多带、非确定性等图灵机变体通常不改变可计算能力，只改变描述便利性或效率分析方式。
- **第八讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第八讲.ppt`，用一句话背：可判定语言存在总会停机并给出是/否答案的算法；可识别语言可能只在接受时保证停机。
- **第九讲**：先想“解决什么问题”，再想“靠什么机制”。定位到 `第九讲.ppt`，用一句话背：不可判定性说明不存在处理所有输入的通用算法，停机问题和归约证明是课程收束重点。

## 4. 考前自测（题目 + 答案）

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

**题 1：这个考点的核心问题是什么？**

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

**题 2：列出这个考点最该背的 3 个抓手。**

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

**题 3：这个考点最容易混淆或出错的地方是什么？**

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

### 自测 2: 第二讲：正则语言与正则表达式

**题 4：这个考点的核心问题是什么？**

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

**题 5：列出这个考点最该背的 3 个抓手。**

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

**题 6：这个考点最容易混淆或出错的地方是什么？**

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

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

**题 7：这个考点的核心问题是什么？**

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

**题 8：列出这个考点最该背的 3 个抓手。**

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

**题 9：这个考点最容易混淆或出错的地方是什么？**

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

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

**题 10：这个考点的核心问题是什么？**

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

**题 11：列出这个考点最该背的 3 个抓手。**

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

**题 12：这个考点最容易混淆或出错的地方是什么？**

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

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

**题 13：这个考点的核心问题是什么？**

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

**题 14：列出这个考点最该背的 3 个抓手。**

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

**题 15：这个考点最容易混淆或出错的地方是什么？**

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

### 自测 6: 第六讲：图灵机基本模型

**题 16：这个考点的核心问题是什么？**

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

**题 17：列出这个考点最该背的 3 个抓手。**

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

**题 18：这个考点最容易混淆或出错的地方是什么？**

答案：图灵机不是现实机器设计图，而是抽象算法能力的边界模型。

### 自测 7: 第七讲：图灵机变体与等价性

**题 19：这个考点的核心问题是什么？**

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

**题 20：列出这个考点最该背的 3 个抓手。**

答案：
- 多带图灵机可由单带图灵机模拟。
- 非确定性图灵机在可识别能力上与确定性模型相关联。
- Church-Turing 思想强调有效算法可由图灵机刻画。

**题 21：这个考点最容易混淆或出错的地方是什么？**

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

### 自测 8: 第八讲：可判定性和可识别性

**题 22：这个考点的核心问题是什么？**

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

**题 23：列出这个考点最该背的 3 个抓手。**

答案：
- 判定器必须对所有输入停机。
- 识别器只要求属于语言的输入最终接受。
- 可判定、可识别和不可识别之间要分清包含关系。

**题 24：这个考点最容易混淆或出错的地方是什么？**

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

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

**题 25：这个考点的核心问题是什么？**

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

**题 26：列出这个考点最该背的 3 个抓手。**

答案：
- 停机问题是经典不可判定问题。
- 归约把已知难问题转换为目标问题，证明目标也难。
- 证明时要说明若目标可判定，则已知不可判定问题也可判定，从而矛盾。

**题 27：这个考点最容易混淆或出错的地方是什么？**

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

## 5. 最后一遍怎么背

1. 先顺着知识脉络背一遍标题，确认自己知道每一章在解决什么问题。
2. 再只看“必背抓手”，能口述就过，卡住就回对应位置。
3. 最后做自测题，答案说不完整的地方就是考前最后要补的点。