CT Review

可计算性理论复习中心

按“有限自动机 -> 正则语言 -> 上下文无关语言 -> 图灵机 -> 可判定性边界”的链条复习，重点理解模型能力为什么逐层增强。

10 张复习卡9 份资料已定位 知识点来源

DFA/NFA正则语言CFGPDA图灵机可判定性

搜索复习内容

10 张卡片可检索。

章节目录

第一讲导引 +（有穷状态自动机）.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

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

概念位置机制题型

第二讲.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

(a|b)*abb 表示所有以 abb 结尾的 a/b 串。

概念位置机制题型

第三讲.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

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

概念位置机制题型

第四讲.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

S -> (S)S | 空可以生成配对括号串。

概念位置机制题型

第五讲.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

读到左括号压栈，读到右括号弹栈，最后栈空说明匹配。

概念位置机制题型

第六讲.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

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

概念位置机制题型

第七讲 .ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

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

概念位置机制题型

第八讲.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

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

概念位置机制题型

第九讲.ppt，全讲

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

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

知识脉络与位置

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

必背抓手

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

难点拆解

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

通俗例子

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

概念位置机制题型

可计算性理论考前总复习.md

10. 考前总复习文档：脱离课件复习版

把本门课的知识脉络、必背抓手、便携记忆点和带答案自测题合在一份文档里，适合临考最后一轮只看这一份。

文档内容

文档位置：pdfs/可计算性理论/可计算性理论考前总复习.md。
复习顺序：先背知识脉络，再背抓手，最后用自测题查漏。
自测题每题都附答案，可脱离 PPT 自己过一遍。

打开方式

打开考前总复习文档
也可以在右侧“资料列表”中打开。

怎么用

如果时间很紧，先做自测题；答不上来的题再回到前面的便携记忆点和必背抓手。

临考节奏

每门课用 20-30 分钟过一遍总复习文档，比重新翻所有课件更省力。

脉络抓手记忆自测

资料列表

可计算性理论考前总复习.md打开
可计算性理论知识点复习大纲.md打开
第一讲导引 +（有穷状态自动机）.pdf打开
第二讲.pdf打开
第三讲.pdf打开
第四讲.pdf打开
第五讲.pdf打开
第六讲.pdf打开
第七讲 .pdf打开
第八讲.pdf打开
第九讲.pdf打开