自动机与可计算性

围绕自动机与可计算性建立可解释、可验证的知识主线。

阅读起点

学习前先阅读：编程语言理论基础学习路线。

全书顺序

本书按知识依赖组织。主线先建立可运行的共同模型，再进入机制、工程边界和生产约束；维护与前沿内容明确标注，不改变主线的学习顺序。

第1章｜形式语言与有限自动机

理解本章形式语言与有限自动机的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 字母表与语言：字符串、连接、闭包与语言运算：理解字母表与语言：字符串、连接、闭包与语言运算的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 确定有限自动机：状态、转移、接受状态与计算：理解确定有限自动机：状态、转移、接受状态与计算的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. DFA 设计：模式识别、状态含义与构造方法：理解DFA 设计：模式识别、状态含义与构造方法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. DFA 最小化：等价状态、分割算法与唯一最小 DFA：理解DFA 最小化：等价状态、分割算法与唯一最小 DFA的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第2章｜非确定性与正则语言

理解本章非确定性与正则语言的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 非确定有限自动机：非确定性、ε 转移与接受：理解非确定有限自动机：非确定性、ε 转移与接受的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. NFA 到 DFA：子集构造、幂集与复杂度：理解NFA 到 DFA：子集构造、幂集与复杂度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 正则表达式：语法、语义、等价性与转换：理解正则表达式：语法、语义、等价性与转换的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 正则语言性质：泵引理、闭包性质与判定算法：理解正则语言性质：泵引理、闭包性质与判定算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第3章｜上下文无关文法与下推自动机

理解本章上下文无关文法与下推自动机的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 上下文无关文法：产生式、推导、语法树与歧义：理解上下文无关文法：产生式、推导、语法树与歧义的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 文法设计：递归、嵌套、平衡括号与解析：理解文法设计：递归、嵌套、平衡括号与解析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 范式：Chomsky 范式、Greibach 范式与转换：理解范式：Chomsky 范式、Greibach 范式与转换的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 下推自动机：栈、转移、接受方式与等价性：理解下推自动机：栈、转移、接受方式与等价性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. CFL 性质：泵引理、闭包性质与判定算法：理解CFL 性质：泵引理、闭包性质与判定算法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第4章｜图灵机与可计算性

理解本章图灵机与可计算性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 图灵机基础：带子、读写头、转移与停机：理解图灵机基础：带子、读写头、转移与停机的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 图灵机设计：子程序、多带、非确定性与等价性：理解图灵机设计：子程序、多带、非确定性与等价性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. Church-Turing 论题：可计算性、有效过程与物理限制：理解Church-Turing 论题：可计算性、有效过程与物理限制的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 编码与通用图灵机：图灵机编码、输入编码与 UTM：理解编码与通用图灵机：图灵机编码、输入编码与 UTM的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第5章｜可判定性与归约

理解本章可判定性与归约的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 可判定性：判定器、识别器、停机与对角化：理解可判定性：判定器、识别器、停机与对角化的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 停机问题：对角化证明、不可判定性与推论：理解停机问题：对角化证明、不可判定性与推论的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 归约：映射归约、计算归约与困难性传递：理解归约：映射归约、计算归约与困难性传递的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. Rice 定理：非平凡性质、语义性质与证明：理解Rice 定理：非平凡性质、语义性质与证明的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 递归定理与自指：自复制、不动点与 Quine：理解递归定理与自指：自复制、不动点与 Quine的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第6章｜复杂度、逻辑与应用（第1段）

理解本章复杂度、逻辑与应用的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 时间复杂度：时间类、多项式、指数与问题分类：理解时间复杂度：时间类、多项式、指数与问题分类的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. P 与 NP：验证、证据、NP 完全与归约链：理解P 与 NP：验证、证据、NP 完全与归约链的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 空间复杂度：PSPACE、L、NL 与可达性：理解空间复杂度：PSPACE、L、NL 与可达性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 逻辑与自动机：命题逻辑、一阶逻辑、模型检验与可满足性：理解逻辑与自动机：命题逻辑、一阶逻辑、模型检验与可满足性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 编译器应用：词法分析、语法分析、正则与 CFG：理解编译器应用：词法分析、语法分析、正则与 CFG的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 形式化验证：模型检验、程序验证与时态逻辑：理解形式化验证：模型检验、程序验证与时态逻辑的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第7章｜复杂度、逻辑与应用（第2段）

理解本章复杂度、逻辑与应用的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. DFA 基础：理解DFA 基础的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 状态设计：理解状态设计的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. NFA：理解NFA的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 子集构造：理解子集构造的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 正则表达式：理解正则表达式的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. CFG 推导：理解CFG 推导的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第8章｜复杂度、逻辑与应用（第3段）

理解本章复杂度、逻辑与应用的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 文法设计：理解文法设计的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 下推自动机：理解下推自动机的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 图灵机基础：理解图灵机基础的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 变体等价性：理解变体等价性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. Church-Turing 论题：理解Church-Turing 论题的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 停机问题：理解停机问题的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第9章｜复杂度、逻辑与应用（第4段）

理解本章复杂度、逻辑与应用的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 归约：理解归约的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. P 与 NP 定义：理解P 与 NP 定义的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. NP 完全：理解NP 完全的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 空间复杂度：理解空间复杂度的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 逻辑与自动机：理解逻辑与自动机的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
6. 可满足性：理解可满足性的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

第10章｜复杂度、逻辑与应用（第5段）

理解本章复杂度、逻辑与应用的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

1. 词法分析：理解词法分析的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
2. 编译器应用：理解编译器应用的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
3. 模型检验：理解模型检验的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
4. 时态逻辑：理解时态逻辑的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。
5. 形式化方法：理解形式化方法的核心模型、常见操作和适用边界，并能据此判断下一步该查什么或如何验证。

阅读边界

本页是学习路线和专题入口，不替代专题笔记中的机制解释、可运行示例和练习。笔记尚未完成的专题会先显示为占位页；已有经验的读者可以跳到具体章节，再按前置关系回补。

路线状态

本路线的目录已完成本轮架构审查；专题笔记的内容质量和来源审查另行进行。