元数据卡
- 前置知识：第十卷（数学基础），尤其集合论与图论基本概念
- 预计时间：40 分钟
- 核心难度：入门
- 阅读模式：高度专注（建议 40 分钟+）
- 完成标志：能说清乔姆斯基谱系的四个层次，能手动构建最简单的有限自动机
"研究造物者的咒语。馆长说'懂了咒语你才能创造新东西'。"你站在咒术高塔的第一层，面前是一道石门，上面刻满了奇怪的符号——有的像字母，有的像箭矢，有的像圆圈里绕来绕去的线。你隐约觉得这些符号之间有一种隐秘的秩序。
你的进度
你从数学塔拿到了基础工具（集合、映射、图论），现在站在咒术高塔的入口。这一层要回答一个根本问题：什么叫"一种语言"？不是口语，不是文字——而是编程语言、配置语言、DSL、乃至正则表达式这些"人造语言"的共同本质是什么。
你的任务
这一章为你建立理解所有"人造语言"的理论框架。你会看到，每种编程语言都可以被归入某个"复杂度的层次"，而编译器的各个阶段正好对应这些层次。先搞清语言的数学定义，再逐层认识乔姆斯基谱系，最后用自动机（一种最简单的计算模型）来体验"检查一个串是否属于某种语言"的直觉。这个过程不需要编程，但需要你静下心来，在纸上多画几个例子。
破局 - 溯源
你站在石门前，门上刻着这样一条规则：
只有念出正确的咒语，石门才会打开。
可"正确的咒语"是什么意思？你试了几个词——"open"、"hello"、"abracadabra"——都没反应。你注意到门的下方有一排小字："所有咒语由字母 a 和 b 组成，且必须以 a 开头，以 b 结尾。"
这其实就定义了一种语言。用数学的话来说：
语言（Language）是某个字母表上所有可能字符串的一个子集。
比如，字母表 ∑ = {a, b}，那所有可能的字符串是无限集合：{ε, a, b, aa, ab, ba, bb, aaa, ...}。而"以 a 开头、以 b 结尾"这个规则，就从中筛选出一个子集——一种语言。
这就是形式语言理论的第一课：精确地定义"什么是有效的"。
乔姆斯基谱系——语言的四个层次
语言学家乔姆斯基发现，所有的形式语言可以被划分为四个层次，每一层对应一种文法（grammar）的类型，也对应着一类自动机（automaton）——也就是能识别这种语言的"机器"。
| 层次 | 文法类型 | 规则形式 | 对应的自动机 | 典型例子 |
|---|---|---|---|---|
| 3型 | 正则文法 | A → aB 或 A → a | 有限自动机（FA） | 正则表达式、词法规则 |
| 2型 | 上下文无关文法 | A → γ | 下推自动机（PDA） | 编程语言的语法结构 |
| 1型 | 上下文有关文法 | αAβ → αγβ | 线性有界自动机（LBA） | 某些自然语言结构 |
| 0型 | 无限制文法 | α → β | 图灵机（TM） | 一切可计算的语言 |
第四层（0型）最强大，第三层（3型）最受限。编译器的各个阶段正好从底层走到顶层：词法分析（3型）→ 语法分析（2型）→ 语义分析（1型的核心）→ 代码生成（0型直觉）。
你不必一次性记下全部四层。先把注意力放在最底层——3型（正则文法），因为它是最小、最可控的建筑积木。
有限自动机——最简单的计算模型
有限自动机只有两个核心：状态和转移。它用有限个状态来记忆"读到哪了"。
一个判断"以 a 开头、以 b 结尾"的有限自动机可以这样画：
状态：q0（起始）、q1（接到过 a）、q2（已结尾")
转移：
q0 --a--> q1
q1 --a--> q1
q1 --b--> q2
q2 --a--> q1
q2 --b--> q2工作过程：
- 读 "ab"：q0 → q1 → q2（接受）
- 读 "aab"：q0 → q1 → q1 → q2（接受）
- 读 "ba"：q0 无法从 q0 出发读 b，停留在 q0（拒绝）
这就是**确定性有限自动机（DFA）**的工作方式。它"确定性"体现在每个状态+输入符号的组合只有一个确定的下一个状态。
非确定性有限自动机（NFA）
NFA 允许一个状态+输入符号对应多个转移，或者存在"epsilon转换"（不用输入就可以跳转）。NFA 看起来"可以猜"——但实际实现时，计算机可以追踪所有可能的状态（子集构造法），证明 NFA 和 DFA 表达能力完全等价。
为什么 NFA 有用：写正则表达式的时候，你自然写出的往往是 NFA（"或者"关系用多条转移表达），而计算机真正运行时需要 DFA。把 NFA 转成 DFA 是正则引擎的核心步骤。
正则语言 vs. 上下文无关语言——边界在哪
正则语言虽然简单好用，但有明确的能力边界。一个经典例子：判断括号是否匹配。
"()" -> 匹配
"(())" -> 匹配
"((())))" -> 不匹配括号匹配需要"记住我开了几个括号"，这需要不受限的计数器。有限自动机只有有限个状态，做不到。所以括号匹配不是正则语言——它需要上下文无关文法（2型）才能表达。
这就是编译器为什么要分成词法和语法两个阶段：词法分析用正则文法（快速、简单、线性时间），语法分析用上下文无关文法（更强大、但也更慢）。
常见陷阱
陷阱一：混淆语言与自动机。"语言是问题，自动机是解法。" 自动机是判断工具，语言是被判断的对象。先定义清楚语言，再选择合适的自动机。
陷阱二：以为 NFA 比 DFA 强大。 NFA 和 DFA 在表达能力上完全等价，只是 NFA 更易写、DFA 更高效。任何 NFA 都可以转换成等价的 DFA（虽然状态数可能指数增长）。
陷阱三：低估正则语言的局限性。 括号匹配、回文判断、数素数——这些都不是正则语言能处理的问题。编写编译器时，词法分析只处理单词级别的结构，不要试图在词法阶段解决语法问题。
通关挑战
- 画一个 DFA，它能识别"所有由 a 和 b 组成、且包含至少一个 a 的字符串"。
- 把上面的 DFA 改写成一个 NFA，然后手动用子集构造法把它转回 DFA。
- 解释为什么"所有由 a 和 b 组成、且 a 的个数等于 b 的个数"不是正则语言。
旅人笔记
形式语言理论的核心一句话：精确描述什么是对的，让机器替你去检查。
下一站预告
理解了最底层的正则语言，下一章会深入 DFA 和 NFA 的构造细节，并让你亲手把正则表达式翻译成自动机。