1_正则语言1.3.ZH解释

这段引言的核心思想是通过类比来帮助我们理解一个全新的概念：正则表达式。它将我们熟悉的算术表达式与即将学习的正则表达式进行对比，揭示它们在结构和求值上的相似与不同之处。

1. 类比的起点：算术表达式
   • 我们从小就学习算术，知道如何使用数字（如 5, 3, 4）和运算符（如 + 和 ×）组合成一个表达式，例如 $(5+3) \times 4$。
   • 这个表达式有一个明确的“值”。通过计算，我们知道 $(5+3) \times 4 = 8 \times 4 = 32$。这个值是一个数字。
2. 引入新概念：正则表达式
   • 现在，我们将这种“构建表达式”的思想迁移到一个新的领域：形式语言理论。
   • 在这个新领域里，我们操作的对象不再是数字，而是“语言”（语言是字符串的集合）。
   • 构建表达式所用的运算符也不同，不再是加号和乘号，而是三种正则运算：并 (Union, 符号是 $\cup$)、连接 (Concatenation, 符号是 $\circ$) 和 星号 (Star, 符号是 $^{*}$)。
   • 使用这些正则运算构建出的表达式，就叫做正则表达式 (Regular Expression)。
3. 一个正则表达式的实例剖析
   • 书中给出了一个例子：$(0 \cup 1) 0^{*}$。
   • 这个表达式看起来有些陌生，但我们可以像分析算术表达式一样拆解它。
   • 核心区别：算术表达式的值是一个数字，而正则表达式的值是一个语言（即一个字符串的集合）。
4. 分步拆解 $(0 \cup 1) 0^{*}$
   • 第一部分：$(0 \cup 1)$
   • 在正则表达式中，单个字符（如 '0' 或 '1'）本身就是一种最简单的正则表达式。
   • 正则表达式 '0' 代表的语言是只包含一个字符串 "0" 的集合，即 $\{0\}$。
   • 同理，正则表达式 '1' 代表的语言是 $\{1\}$。
   • 符号 $\cup$ 是并运算，它对语言（集合）进行操作。所以，$(0 \cup 1)$ 的含义是 $L(0) \cup L(1)$，也就是 $\{0\} \cup \{1\}$。
   • 这个并集的结果是一个新的语言：$\{0, 1\}$。这个语言包含两个字符串："0" 和 "1"。
   • 第二部分：$0^{*}$
   • 符号 $^{*}$ 是星号运算，也叫克林闭包 (Kleene Star)。它作用于一个语言。
   • $0^{*}$ 表示对语言 $\{0\}$ 进行星号运算，即 $\{0\}^{*}$。
   • 一个语言的星号运算结果是：从该语言中任意选取 0 个、1 个、2 个、...、n 个字符串，并按任意顺序连接起来形成的所有可能的新字符串的集合。
   • 对于 $\{0\}^{*}$：
   • 选 0 个字符串：得到空字符串 $\varepsilon$。
   • 选 1 个字符串：得到 "0"。
   • 选 2 个字符串：得到 "0" 连接 "0"，即 "00"。
   • 选 3 个字符串：得到 "000"。
   • ... 以此类推。
   • 所以，$0^{*}$ 所代表的语言是 $\{\varepsilon, 0, 00, 000, \dots\}$，即包含任意数量（包括零个）0 的字符串的集合。
   • 第三部分：连接运算
   • 在算术中，乘法符号 $\times$ 有时可以省略，比如 $4a$ 表示 $4 \times a$。
   • 在正则表达式中，连接 (concatenation) 运算符 $\circ$ 也通常被省略。
   • 因此，表达式 $(0 \cup 1) 0^{*}$ 的完整写法是 $(0 \cup 1) \circ 0^{*}$。
   • 连接运算的作用是：从第一个语言中取出一个字符串，从第二个语言中取出一个字符串，然后将它们拼接在一起。结果是所有这种拼接可能性的集合。
   • 在这里，就是从语言 $\{0, 1\}$ 中取一个字符串，再从语言 $\{\varepsilon, 0, 00, \dots\}$ 中取一个字符串，进行拼接。
   • 让我们看看拼接结果：
   • 取 "0" 和 $\varepsilon$ $\rightarrow$ "0"。
   • 取 "0" 和 "0" $\rightarrow$ "00"。
   • 取 "0" 和 "00" $\rightarrow$ "000"。
   • ...
   • 取 "1" 和 $\varepsilon$ $\rightarrow$ "1"。
   • 取 "1" 和 "0" $\rightarrow$ "10"。
   • 取 "1" 和 "00" $\rightarrow$ "100"。
   • ...
   • 将所有这些结果汇集起来，得到的语言是 $\{0, 00, 000, \dots, 1, 10, 100, \dots\}$。
   • 这个语言可以用一句话描述：所有以一个 '0' 或一个 '1' 开头，后面跟着任意数量（包括零个）的 '0' 的字符串的集合。

这一段从理论转向了实践，阐述了正则表达式的现实意义和广泛应用。它告诉我们，正则表达式不仅仅是理论家们在象牙塔里研究的抽象概念，更是程序员和计算机用户日常工作中不可或缺的强大工具。

1. 核心应用领域：文本处理和模式匹配
   • 我们每天都在和文本打交道：代码、日志文件、网页、文档等等。
   • 很多时候，我们需要的不是一个特定的、一成不变的字符串，而是一类符合某种“模式”的字符串。
   • 例如，我想在一个文件中找到所有的电子邮件地址。电子邮件地址的模式是什么？通常是“一串字符 @ 另一串字符 . 顶级域名”。这个模式用普通文本搜索是无法完成的。
   • 正则表达式正是为了解决这类问题而生。它提供了一种精确、灵活的语言来定义这些模式。
2. 具体的工具和编程语言
   • UNIX/Linux 工具:
   • grep: 这是 Global Regular Expression Print 的缩写，是UNIX系统中最经典的文件搜索工具。它的核心功能就是使用正则表达式在文件中查找匹配的行。例如，grep "error" log.txt 会找出 log.txt 中所有包含 "error" 的行。而 grep "^[0-9]" data.txt 则会使用更复杂的正则表达式找出所有以数字开头的行。
   • awk: 这是一个更强大的文本处理工具，它能将文件逐行读入，并使用正则表达式对行中的字段进行匹配和处理。
   • 编程语言:
   • Perl: 这门语言因其强大的内置正则表达式功能而闻名，被誉为文本处理的“瑞士军刀”。在Perl中，正则表达式是一等公民，使用起来非常自然和高效。
   • 几乎所有现代编程语言，如 Python, Java, JavaScript, C#, Ruby, Go 等，都内置了对正则表达式的支持（通常通过标准库提供）。这使得开发者可以在自己的程序中轻松实现复杂的文本匹配、验证、替换和提取功能。
   • 文本编辑器:
   • 像 VS Code, Sublime Text, Vim, Emacs 等专业的文本编辑器，它们的查找和替换功能都支持正则表达式模式。这对于批量修改代码或文本格式非常有用。例如，你可以用一个正则表达式一次性将所有 var name = "value"; 格式的变量声明替换为 const name = "value";。

这个示例和后续的段落通过一系列具体的正则表达式，进一步深化我们对正则运算的理解，并引入了运算符优先级的重要概念。

1. 核心示例：$(0 \cup 1)^{*}$
   • 这是一个非常基础且重要的正则表达式。让我们再次分解它。
   • 内部: $(0 \cup 1)$。我们已经知道，它描述的语言是 $\{0, 1\}$。这个语言包含了所有长度为 1 的、由 0 和 1 组成的字符串。
   • 外部: $^{*}$（星号运算）。这个运算作用于语言 $\{0, 1\}$。
   • 星号运算的含义是：从基础语言（这里是 $\{0, 1\}$）中，任意挑选 0 次、1 次、2 次、...、n 次字符串，然后把它们拼接起来。
   • 推演过程:
   • 挑选 0 次: 得到空字符串 $\varepsilon$。
   • 挑选 1 次: 可以选 "0"，也可以选 "1"。得到 $\{0, 1\}$。
   • 挑选 2 次: 可能的组合有 "0"后面跟"0" (00), "0"后面跟"1" (01), "1"后面跟"0" (10), "1"后面跟"1" (11)。得到 $\{00, 01, 10, 11\}$。
   • 挑选 3 次: 得到所有长度为 3 的二进制字符串，如 "000", "001", ..., "111"。
   • ... 以此类推。
   • 结论: 将所有这些可能的结果集合在一起，我们就得到了由 '0' 和 '1' 构成的所有可能的字符串，包括空字符串。这正是字母表 $\Sigma=\{0,1\}$ 上所有字符串的集合，通常记作 $\Sigma^{*}$。
2. 引入简写符号 $\Sigma$
   • 字母表 (Alphabet) $\Sigma$ 是一个字符的有限集合。在我们的例子中，$\Sigma = \{0, 1\}$。
   • 书中提出了一个方便的简写：当我们在正则表达式中写 $\Sigma$ 时，它就等同于 $(0 \cup 1 \cup \dots)$，即字母表中所有单个字符的并集。
   • 所以，如果 $\Sigma = \{0, 1\}$，那么正则表达式 $\Sigma$ 就等同于 $(0 \cup 1)$。它描述的语言是 $\{0, 1\}$，即所有长度为 1 的字符串。
   • 相应地，正则表达式 $\Sigma^{*}$ 就等同于 $(0 \cup 1)^{*}$，它描述的语言是 $\Sigma^{*}$，即该字母表上的所有字符串。
3. 利用简写构建更复杂的表达式
   • $\Sigma^{*} 1$:
   • 这是两个正则表达式 $\Sigma^{*}$ 和 $1$ 的连接。
   • $L(\Sigma^{*})$ 是所有由 '0' 和 '1' 组成的字符串的语言。
   • $L(1)$ 是语言 $\{1\}$。
   • 连接它们：从 $L(\Sigma^{*})$ 中取一个字符串 $w$，然后在其末尾拼接上一个 '1'。
   • 例如：取 $\varepsilon$ 拼接 '1' $\rightarrow$ "1"；取 "0" 拼接 '1' $\rightarrow$ "01"；取 "101" 拼接 '1' $\rightarrow$ "1011"。
   • 这个表达式描述的语言是：所有以 '1' 结尾的字符串。
   • $(0 \Sigma^{*}) \cup (\Sigma^{*} 1)$:
   • 这是一个并集，由两部分组成。
   • 第一部分 $0 \Sigma^{*}$: 描述所有以 '0' 开头的字符串。 (例如: "0", "01", "0011"...)
   • 第二部分 $\Sigma^{*} 1$: 描述所有以 '1' 结尾的字符串。 (例如: "1", "01", "1101"...)
   • 并集 $\cup$: 将这两个语言（集合）合并。一个字符串只要满足其中至少一个条件，就属于这个语言。
   • 例如: "0110" 属于该语言（因为它以 '0' 开头）。"1101" 属于该语言（因为它以 '1' 结尾）。"01" 属于该语言（因为它既以 '0' 开头，又以 '1' 结尾）。"10" 则不属于该语言（因为它以 '1' 开头，以 '0' 结尾，两个条件都不满足）。
   • 所以，这个表达式描述的语言是：所有以 '0' 开头或以 '1' 结尾的字符串。
4. 引入运算符优先级
   • 这个概念和算术完全一样，是为了在没有括号时消除歧义。
   • 算术优先级: 乘法($\times$) > 加法($+$)。$2+3 \times 4$ 被解释为 $2+(3 \times 4)$。
   • 正则表达式优先级:
5. 最高: 星号 ($^{*}$)
6. 次高: 连接 ($\circ$)
7. 最低: 并 ($\cup$)
   • 这意味着，当你看到一个没有括号的正则表达式时，要先处理所有的星号，然后处理所有的连接，最后处理所有的并。
   • 例如：$a \cup b c^{*}$
   • 首先计算 $c^{*}$，得到语言 $L(c^{*})$。
   • 然后计算 $b \circ (c^{*})$，得到语言 $L(bc^{*})$。
   • 最后计算 $a \cup (bc^{*})$，得到最终的语言 $L(a) \cup L(bc^{*})$。
   • 括号的作用: 括号可以覆盖默认的优先级。$(a \cup b)c^{*}$ 则会先计算 $a \cup b$，得到语言 $L(a \cup b)$，然后再对此语言进行星号运算。这和 $a \cup bc^{*}$ 是完全不同的。

这是对正则表达式的一个形式化、递归的定义。这种定义方式在数学和计算机科学中非常常见，它通过两种方式来确定一个对象是否属于某个集合：

1. 基础情况 (Base Cases): 定义最简单、最基本的成员。
2. 归纳/递归步骤 (Inductive/Recursive Steps): 定义如何从已有的成员通过某些规则组合出新的、更复杂的成员。

让我们逐条拆解这个定义：

基础情况 (原子正则表达式)

这三条定义了构成所有正则表达式的最基本“积木”，它们自身就是正则表达式，不能再被分解。

• 1. 字母表中的符号 $a$:
• 含义: 字母表 $\Sigma$ 中的任何一个单独的符号（比如 'a', 'b', '0', '1'）都是一个合法的正则表达式。
• 它描述的语言: 这个正则表达式 $a$ 所描述的语言是 $L(a) = \{a\}$，一个只包含单个字符串 $a$ 的集合。
• 例子: 如果 $\Sigma = \{0, 1\}$，那么 0 是一个正则表达式，1 也是一个正则表达式。

• 2. 空字符串符号 $\varepsilon$:
• 含义: 符号 $\varepsilon$ 本身就是一个合法的正则表达式。
• 它描述的语言: 它描述的语言是 $L(\varepsilon) = \{\varepsilon\}$，一个只包含空字符串的集合。
• 注意: 空字符串不是“没有东西”，它是一个实际存在的、长度为零的字符串。

• 3. 空集符号 $\emptyset$:
• 含义: 符号 $\emptyset$ 本身就是一个合法的正则表达式。
• 它描述的语言: 它描述的语言是 $L(\emptyset) = \{\}$，即空语言，一个不包含任何字符串的集合。
• 与 $\varepsilon$ 的区别: 这是初学者极易混淆的地方。$L(\varepsilon)$ 是一个包含 一个 元素的集合（这个元素是空字符串），而 $L(\emptyset)$ 是一个包含 零个 元素的集合。想象一个钱包，$L(\varepsilon)$ 是钱包里有一张 0 元的钞票，而 $L(\emptyset)$ 是钱包里什么都没有，是空的。

归纳/递归步骤 (复合正则表达式)

这三条定义了如何使用正则运算，将已经存在的正则表达式组合成新的、更复杂的正则表达式。

• 4. 并 (Union): $(R_1 \cup R_2)$
• 含义: 如果你已经有了两个合法的正则表达式 $R_1$ 和 $R_2$，那么用括号把它们的并运算括起来，即 $(R_1 \cup R_2)$，得到的结果也是一个合法的正则表达式。
• 它描述的语言: 新表达式描述的语言是两个子表达式所描述语言的并集，即 $L(R_1 \cup R_2) = L(R_1) \cup L(R_2)$。
• 例子: 因为 0 和 1 都是正则表达式，所以 (0 U 1) 也是一个正则表达式。

• 5. 连接 (Concatenation): $(R_1 \circ R_2)$
• 含义: 如果 $R_1$ 和 $R_2$ 是正则表达式，那么将它们用连接符号 $\circ$ 连接并用括号括起来，即 $(R_1 \circ R_2)$，也是一个合法的正则表达式。在实践中，$\circ$ 和外层括号常常省略。
• 它描述的语言: 新表达式描述的语言是两个子语言的连接，即从 $L(R_1)$ 中取一个字符串，后面拼接上一个从 $L(R_2)$ 中取的字符串。
• 例子: 因为 (0 U 1) 和 0 都是正则表达式，所以 ((0 U 1) o 0) 也是一个正则表达式。

• 6. 星号 (Star): $(R_1^*)$
• 含义: 如果 $R_1$ 是一个正则表达式，那么在它后面加上星号并用括号括起来，即 $(R_1^*)$，也是一个合法的正则表达式。
• 它描述的语言: 新表达式描述的语言是子语言 $L(R_1)$ 的克林闭包（Kleene Star），即从 $L(R_1)$ 中取任意 0 个或多个字符串进行拼接得到的所有字符串的集合。
• 例子: 因为 0 是正则表达式，所以 (0*) 也是一个正则表达式。

递归的本质

这个定义是递归的，因为规则 4, 5, 6 在定义“什么是正则表达式”时，引用了“正则表达式”自身。但这不是一个无效的循环定义，因为用于构建新表达式的 $R_1$ 和 $R_2$ 总是比生成的表达式 $(R_1 \cup R_2)$ 要“更小”或“更简单”。我们可以从最基础的原子表达式（a, $\varepsilon$, $\emptyset$）出发，像搭乐高积木一样，一层一层地构建出任意复杂的正则表达式。

这段内容是对定义 1.52 的进一步阐释和说明，主要解决了两个问题：一是明确正则表达式与其所代表语言之间的关系；二是解释为什么这个定义是有效的，而不是一个无效的循环定义。

1. 正则表达式与语言的映射关系
   • 核心思想: 正则表达式本身是一个“符号序列”或“句法结构”，而它的“意义”或“值”是一个语言（即一个字符串的集合）。这就像算术表达式 (5+3)*4 是一个符号序列，而它的值是数字 32。
   • 基础情况的映射:
   • 正则表达式 a $\rightarrow$ 语言 $\{a\}$
   • 正则表达式 ε $\rightarrow$ 语言 $\{\varepsilon\}$
   • 正则表达式 ∅ $\rightarrow$ 语言 ∅ 或 {} (空集)
   • 归纳步骤的映射:
   • 正则表达式 $(R_1 \cup R_2)$ $\rightarrow$ 语言 $L(R_1) \cup L(R_2)$
   • 正则表达式 $(R_1 \circ R_2)$ $\rightarrow$ 语言 $L(R_1) \circ L(R_2)$
   • 正则表达式 $(R_1^*)$ $\rightarrow$ 语言 $(L(R_1))^*$
   • 这里的关键是，正则运算符（$\cup, \circ, ^{*}$）既可以看作是组合正则表达式的语法符号，也可以看作是作用于语言（集合）的实际运算。形式化定义是在语法层面定义的，而这里是在语义（意义）层面进行解释。
2. 辨析 $\varepsilon$ 和 $\emptyset$
   • 这部分内容是对前面易错点的再次强调，因为它非常重要且容易混淆。
   • 正则表达式 $\varepsilon$:
   • 它描述的语言是 $L(\varepsilon) = \{\varepsilon\}$。
   • 这是一个非空的语言。它包含一个成员，这个成员就是空字符串 ε。
   • 类比: 一个钱包里有一张“零元”的纸币。钱包不是空的，它里面有东西。
   • 正则表达式 $\emptyset$:
   • 它描述的语言是 $L(\emptyset) = \{\}$。
   • 这是一个空语言（空集）。它里面没有任何成员，一个字符串也没有。
   • 类比: 一个空钱包。里面什么都没有。
3. 归纳定义的有效性
   • 潜在的问题（循环定义）: 有人可能会质疑，规则 4 说“如果 $R_1, R_2$ 是正则表达式，那么 $(R_1 \cup R_2)$ 也是正则表达式”，这听起来像是在用“正则表达式”这个词来定义它自己，陷入了“鸡生蛋还是蛋生鸡”的困境。
   • 解答（归纳的本质）: 这不是一个无效的循环，因为用于构建的组件 ($R_1, R_2$) 总是比最终的产物 ($R$) “更小”或“更简单”。
   • “更小”可以从结构上理解。比如，表达式 (a U b) 的长度是 5 (包括括号)，而它的组件 a 和 b 的长度都是 1。
   • “更简单”可以从构建的层级来理解。我们总是从第 0 层的原子表达式（a, ε, ∅）开始，然后用它们构建第 1 层的表达式（如 (a U b)），再用第 0 层和第 1 层的表达式构建第 2 层的表达式（如 ((a U b)*)），以此类推。
   • 避免了循环: 因为我们永远是用已经定义好或构建好的、更简单的东西去定义更复杂的新东西，所以这个过程是有方向、有终点的，它会终止于最基础的原子表达式，从而避免了无限循环。
   • 名称: 这种依赖于更小自身实例来定义新实例的方法，在逻辑和数学中被称为归纳定义 (Inductive Definition)。

这一部分引入了几个非常有用的简写符号（语法糖, Syntactic Sugar），并正式提出了一个表示法来区分正则表达式本身和它所描述的语言。

1. 正闭包 (Positive Closure) $R^{+}$
   • 定义: $R^{+}$ 是 $R R^{*}$ 的简写。
   • 拆解:
   • $R$ 代表从语言 $L(R)$ 中取一个字符串。
   • $R^{*}$ 代表从语言 $L(R)$ 中取 0 个或多个字符串进行拼接。
   • $R R^{*}$ (即 $R \circ R^{*}$) 表示，先从 $L(R)$ 中取一个字符串（这是 $R$ 的部分），然后从 $L(R^{*})$ 中再取一个字符串（这是 $R^{*}$ 的部分），把它们拼接起来。
   • 实际效果:
   • $L(R^{*}) = \{\text{0次拼接}\}\ \cup\ \{\text{1次或多次拼接}\}$
   • $L(R) \circ L(R^{*}) = L(R) \circ (\{\varepsilon\} \cup L(R^{+})) = (L(R) \circ \{\varepsilon\}) \cup (L(R) \circ L(R^{+})) = L(R) \cup \dots$
   • 一个更直观的理解是：$R R^{*}$ 的结果，必然至少包含一个来自 $R$ 的连接。这恰好就是 “1 次或更多次连接” 的含义。
   • 与 $R^{*}$ 的关系:
   • $R^{*}$：代表 “0 次或多次” 的连接。
   • $R^{+}$：代表 “1 次或多次” 的连接。
   • 它们唯一的区别就在于是否包含 “0 次连接” 的情况，即空字符串 $\varepsilon$。
   • 因此，我们有这个非常重要的关系：$L(R^{*}) = L(R^{+}) \cup \{\varepsilon\}$。反过来写就是 $R^{+} \cup \varepsilon=R^{*}$。
2. 幂次运算 $R^{k}$
   • 定义: $R^{k}$ 是 $k$ 个 $R$ 连接在一起的简写。
   • 展开形式: $R^{k} = \underbrace{R \circ R \circ \dots \circ R}_{k \text{ 个}}$
   • 它描述的语言: 从语言 $L(R)$ 中取 $k$ 个字符串，依次拼接起来。
   • 例子:
   • $R^2 = R \circ R$。$L(R^2)$ 就是从 $L(R)$ 中取两个字符串 $w_1, w_2$ 拼接成 $w_1w_2$ 的所有可能。
   • $R^3 = R \circ R \circ R$。
   • $R^1 = R$。
   • $R^0 = \varepsilon$。这是约定俗成的定义，代表 0 次连接，其结果是空字符串。
3. 语言表示法 $L(R)$
   • 动机: 到目前为止，我们一直在正则表达式（比如 0*）和它所描述的语言（比如 {ε, 0, 00, ...} ）之间切换。有时这种混用会产生歧义。
   • 定义: 为了严格区分，我们引入记号 $L(R)$。
   • $R$：指正则表达式这个句法结构本身，它是一串符号。
   • $L(R)$：指正则表达式 $R$ 所描述的那个语言，它是一个字符串的集合。
   • 作用: 这个记号在进行理论推导和证明时非常有用，可以使论述更加严谨。例如，我们可以清晰地写出并运算的语义：$L(R_1 \cup R_2) = L(R_1) \cup L(R_2)$。左边的 $\cup$ 是正则表达式语法的一部分，而右边的 $\cup$ 是集合论中的并集运算。

这一部分混合了几个要点：首先通过一组恒等式来深化对 $\varepsilon$ 和 $\emptyset$ 的理解，然后给出一个复杂的、实际应用中的正则表达式例子（数值常量），并最终点出正则表达式在编译器设计中的核心角色——定义词法单元并生成词法分析器。

1. 重要的恒等式
   • 这些恒等式揭示了 $\varepsilon$ 和 $\emptyset$ 在正则运算中扮演着类似于算术中 1 和 0 的角色，但又不完全相同。
   • $R \cup \emptyset = R$:
   • 语义: $L(R \cup \emptyset) = L(R) \cup L(\emptyset) = L(R) \cup \{\}$。一个集合与一个空集取并集，结果还是原来的集合。
   • 类比: 这就像算术中的 x + 0 = x。$\emptyset$ 在并运算中是“单位元”。
   • $R \circ \varepsilon = R$:
   • 语义: $L(R \circ \varepsilon) = L(R) \circ L(\varepsilon) = L(R) \circ \{\varepsilon\}$。将一个语言中的每个字符串 $w$ 与空字符串 $\varepsilon$ 连接，结果仍然是 $w$ ($w\varepsilon = w$)。所以语言不变。
   • 类比: 这就像算术中的 x * 1 = x。$\varepsilon$ 在连接运算中是“单位元”。
2. 打破对称性：交换 $\varepsilon$ 和 $\emptyset$
   • 这里展示了为什么不能简单地将 $\varepsilon$ 和 $\emptyset$ 互换。
   • $R \cup \varepsilon$ 可能不等于 $R$:
   • 语义: $L(R \cup \varepsilon) = L(R) \cup \{\varepsilon\}$。这个操作向语言 $L(R)$ 中添加了空字符串 $\varepsilon$。
   • 例子: 如果 $R=0$，$L(R)=\{0\}$。那么 $L(R \cup \varepsilon) = \{0\} \cup \{\varepsilon\} = \{0, \varepsilon\}$。显然 $\{0\} \neq \{0, \varepsilon\}$。
   • 什么时候相等？: 只有当 $L(R)$ 本身已经包含了 $\varepsilon$ 时，等式才成立。
   • $R \circ \emptyset$ 可能不等于 $R$:
   • 语义: $L(R \circ \emptyset) = L(R) \circ L(\emptyset) = L(R) \circ \{\}$。将一个语言与空语言进行连接。因为无法从空语言中取出任何字符串进行拼接，所以结果是空语言 $\emptyset$。
   • 例子: 如果 $R=0$，$L(R)=\{0\}$。那么 $L(R \circ \emptyset) = \{0\} \circ \{\} = \{\}$。显然 $\{0\} \neq \{\}$。
   • 类比: 这就像算术中的 x * 0 = 0。$\emptyset$ 在连接运算中是“零元”，它具有“吞噬”一切的特性。
3. 实际应用：定义数值常量
   • 这里给出了一个非常实用的正则表达式，用于描述编程语言中常见的数字格式。
   • 表达式: $(+\cup-\cup \varepsilon)\left(D^{+} \cup D^{+} . D^{*} \cup D^{*} . D^{+}\right)$
   • 字母表: $D = \{0,1,2,3,4,5,6,7,8,9\}$。
   • 分解:
   • 第一部分: $(+\cup-\cup \varepsilon)$
   • 这部分描述数字的符号。
   • 它可以是 +，或者是 -，或者什么都没有 (ε)。
   • 匹配 +, - 或空。
   • 第二部分: $\left(D^{+} \cup D^{+} . D^{*} \cup D^{*} . D^{+}\right)$
   • 这部分描述数字本身，由三个用并运算连接的子模式组成。
   • 子模式1: $D^{+}$
   • $D$ 代表任一数字 (0 | 1 | ... | 9)。
   • $D^{+}$ 表示“一个或多个数字”。
   • 这匹配的是整数，如 72。
   • 子模式2: $D^{+} . D^{*}$
   • $D^{+}$: 小数点前至少有一个数字。
   • .: 小数点本身 (注意，在很多正则引擎里 . 是特殊字符，需要转义成 \.，但这里是理论描述，就直接写了)。
   • $D^{*}$: 小数点后有零个或多个数字。
   • 这匹配的是 72. 或 3.14159 这样的数。
   • 子模式3: $D^{*} . D^{+}$
   • $D^{*}$: 小数点前有零个或多个数字。
   • .: 小数点。
   • $D^{+}$: 小数点后至少有一个数字。
   • 这匹配的是 .01 或 0.01 这样的数。
   • 组合: 整个表达式的含义是：一个可选的符号，后面跟着一个数字部分，这个数字部分可以是整数、或者带有小数点的浮点数。
   • 示例匹配:
   • 72: 符号部分匹配 $\varepsilon$，数字部分匹配 $D^{+}$。
   • 3.14159: 符号部分匹配 $\varepsilon$，数字部分匹配 $D^{+} . D^{*}$。
   • +7.: 符号部分匹配 +，数字部分匹配 $D^{+} . D^{*}$。
   • -.01: 符号部分匹配 -，数字部分匹配 $D^{*} . D^{+}$。
4. 在编译器中的角色：词法分析
   • 编译器 (Compiler): 将人类编写的高级语言代码（如 C++, Java）翻译成计算机可以执行的机器代码的程序。
   • 词法单元 (Token): 编程语言中最小的有意义的语法单位。就像英语中的单词。例如，在代码 int x = 10; 中，int, x, =, 10, ; 都是词法单元。
   • 词法分析器 (Lexical Analyzer / Lexer / Scanner): 编译器的第一个部分。它的工作就是读取原始的源代码文本（一长串字符），然后将其切分成一个个的词法单元。
   • 正则表达式的作用: 正则表达式正是用来定义每一种词法单元的模式的。
   • 变量名 (Identifier): (a-zA-Z_)(a-zA-Z0-9_)* (以字母或下划线开头，后跟任意数量的字母、数字或下划线)
   • 整数: [0-9]+
   • 关键字: if, else, while (可以直接匹配)
   • 操作符: +, -, *, /, =
   • 自动化: 一旦我们为一门编程语言的所有词法单元都写好了正则表达式，就可以使用像 Lex 或 Flex 这样的自动化工具，它们会读取这些正则表达式，并自动生成一个高效的词法分析器程序。

这是本章乃至整个计算理论的一个核心结论。它在两个看似完全不同的世界——正则表达式的世界和有限自动机的世界——之间建立了一座坚固的桥梁。

1. 两个世界的对比
   • 有限自动机 (Finite Automata - FA):
   • 本质: 一种计算模型，可以想象成一个带有状态和转换规则的机器。
   • 工作方式: 它一次读取输入字符串的一个字符，并根据当前状态和读到的字符，“跳转”到下一个状态。当字符串读完后，如果机器停在接受状态，则该字符串被“接受”。
   • 描述方式: 声明式 (Declarative) 或 操作式 (Operational)。它通过一系列操作步骤来定义一个语言。我们用状态转换图来可视化它。
   • 正则表达式 (Regular Expressions - RE):
   • 本质: 一种描述字符串模式的代数表达式。
   • 工作方式: 它通过并、连接、星号等运算来组合字符，从而定义一个语言。
   • 描述方式: 代数式 (Algebraic) 或 描述式 (Descriptive)。它直接描述了一个语言的结构。
2. 令人惊讶的等价性
   • 从表面上看，一个像流程图一样的有限自动机和一个像数学公式一样的正则表达式，两者毫无共同之处。
   • “等价”这个词在这里有非常精确的含义：对于任何一个能被有限自动机识别的语言，我们都能找到一个正则表达式来描述它；反之，对于任何一个能被正则表达式描述的语言，我们也都能构造出一个有限自动机来识别它。
   • 这意味着，有限自动机和正则表达式只是描述同一类语言——即正则语言 (Regular Languages)——的两种不同方式。它们是同一枚硬币的两面。
3. 定理 1.54 的陈述
   • 定理: 一个语言是正则语言当且仅当某个正则表达式描述它。
   • 这是一个“当且仅当”(if and only if, iff) 的陈述，意味着它包含两个方向的证明：
   • 方向一 (充分性): 如果一个语言可以被正则表达式描述，那么它是一个正则语言。
   • 要证明这一点，我们需要展示如何将任意一个正则表达式 $R$ 转换成一个能识别语言 $L(R)$ 的有限自动机 (特别是 NFA，因为 NFA 更容易构造)。
   • 方向二 (必要性): 如果一个语言是正则语言，那么它一定能被某个正则表达式描述。
   • 正则语言的定义是“能被有限自动机（DFA）识别的语言”。
   • 所以，要证明这一点，我们需要展示如何将任意一个 DFA 转换成一个等价的正则表达式。
   • 这两个方向的证明将作为两个独立的引理在后面给出。

这是定理 1.54 第一个方向的证明。它旨在说明，任何正则表达式所描述的语言都是正则语言。证明的核心策略是一个构造性证明：它提供了一个具体的算法，能够将任意给定的正则表达式 $R$ 转换成一个识别相同语言 $L(R)$ 的 NFA。

1. 证明的逻辑链
   • 前提: 我们有一个正则表达式 $R$，它描述了语言 $A$ (即 $L(R) = A$)。
   • 目标: 证明 $A$ 是一个正则语言。
   • 回顾正则语言的定义: 一个语言是正则语言，如果存在一个 DFA 识别它。
   • 回顾 NFA 与 DFA 的关系 (推论 1.40): 任何能被 NFA 识别的语言都是正则语言（因为任何 NFA 都能被转换成一个等价的 DFA）。
   • 证明策略: 我们只需要展示如何为任意正则表达式 $R$ 构造一个等价的 NFA。只要能做到这一点，根据推论 1.40，语言 $L(R)$ 就是正则语言，引理得证。
2. 构造方法：模仿正则表达式的归纳定义
   • 正则表达式是通过归纳定义的，它有 3 个基础情况和 3 个归纳步骤。我们的构造算法将完美地模仿这个结构。我们将为每一种情况给出一个构造 NFA 的方法。
   • 这种方法保证了我们可以处理任意复杂的正则表达式，因为任何正则表达式都可以被分解成这六种基本情况之一。
3. 处理基础情况 (原子正则表达式)
   • 情况 1: $R = a$
   • 语言: $L(R) = \{a\}$，只包含单个字符串 a。
   • NFA 构造: 我们需要一个 NFA，它只接受字符串 a。
   • 创建一个起始状态 $q_1$。
   • 创建一个接受状态 $q_2$。
   • 从 $q_1$ 到 $q_2$ 画一个箭头，并用符号 a 标记它。
   • 工作原理:
   • 输入 a: 从 $q_1$ 开始，读到 a，沿着箭头到达 $q_2$。字符串结束，机器在接受状态，所以 a 被接受。
   • 输入任何其他字符串 (如 b, aa, $\varepsilon$): 机器无法从 $q_1$ 离开（或无法匹配完整），最终无法停在接受状态 $q_2$。所以其他字符串都被拒绝。
   • 与 DFA 的区别: 这个构造出的机器是一个 NFA，因为它不是对所有状态和所有输入符号都有定义转换。例如，在 $q_1$，如果输入是 b (假设 $b \neq a$)，没有对应的转换箭头。这在 DFA 中是不允许的（DFA 需要一个完整的转换函数），但在 NFA 中是合法的（缺失的转换被认为是指向一个“死亡状态”）。选择构造 NFA 是因为它更简单、更灵活。

• 情况 2: $R = \varepsilon$
• 语言: $L(R) = \{\varepsilon\}$，只包含空字符串。
• NFA 构造: 我们需要一个 NFA，它只接受空字符串。
• 创建一个起始状态 $q_1$。
• 让这个起始状态 $q_1$ 同时也是一个接受状态。
• 工作原理:
• 输入 $\varepsilon$: 机器从 $q_1$ 开始，字符串立即结束。此时机器在接受状态 $q_1$ 上，所以 $\varepsilon$ 被接受。
• 输入任何非空字符串 (如 a): 机器从 $q_1$ 开始，读到 a，但没有任何地方可以去。字符串未读完机器就卡住了，所以 a 被拒绝。

• 情况 3: $R = \emptyset$
• 语言: $L(R) = \{\}$，即空语言，不接受任何字符串。
• NFA 构造: 我们需要一个不接受任何东西的 NFA。
• 创建一个起始状态 $q$。
• 不要设置任何接受状态。
• 工作原理: 无论输入什么字符串，机器运行结束后，它所在的最终状态都不可能是接受状态（因为根本就没有接受状态），所以任何字符串都会被拒绝。

这部分内容处理了引理 1.55 证明的归纳步骤。它解释了如何为由并、连接和星号三种正则运算构成的复合正则表达式来构造 NFA。

1. 归纳假设 (Inductive Hypothesis)
   • 这个证明方法的核心是归纳。当我们处理 $R = R_1 \cup R_2$ 时，我们假设我们已经知道如何为它的子表达式 $R_1$ 和 $R_2$ 构造出对应的 NFA。
   • 设 NFA $N_1$ 识别 $L(R_1)$，NFA $N_2$ 识别 $L(R_2)$。我们的任务是，利用 $N_1$ 和 $N_2$ 这两个已有的“积木”，来搭建一个新的、更大的 NFA $N$，使得 $N$ 能够识别语言 $L(R_1 \cup R_2)$。
2. 引用已有的结论
   • 作者在这里指出，我们其实已经做过这项工作了。在之前学习“正则语言的封闭性”时，我们已经证明了：
   • 如果 $L_1$ 和 $L_2$ 是正则语言，那么它们的并集 $L_1 \cup L_2$ 也是正则语言。
   • 如果 $L_1$ 和 $L_2$ 是正则语言，那么它们的连接 $L_1 \circ L_2$ 也是正则语言。
   • 如果 $L_1$ 是正则语言，那么它的星号 $L_1^*$ 也是正则语言。
   • 当时的证明就是构造性的：我们给出了具体的算法，展示了如何从识别 $L_1$ 和 $L_2$ 的自动机出发，构造出识别新语言的自动机。
   • 现在，我们直接“重用”那些构造方法。
3. 三种归纳情况的构造方法回顾
   • 情况 4: $R = R_1 \cup R_2$ (并)
   • 目标: 构造一个 NFA $N$ 来识别 $L(N_1) \cup L(N_2)$。
   • 构造 (Thompson's Construction 算法):
4. 创建一个新的起始状态 $q_{new\_start}$。
5. 从 $q_{new\_start}$ 画两条 $\varepsilon$-转移箭头，分别指向 $N_1$ 的起始状态和 $N_2$ 的起始状态。
6. 创建一个新的接受状态 $q_{new\_accept}$。
7. 从 $N_1$ 的所有接受状态画 $\varepsilon$-转移箭头到 $q_{new\_accept}$。
8. 从 $N_2$ 的所有接受状态画 $\varepsilon$-转移箭头到 $q_{new\_accept}$。
9. 将 $N_1$ 和 $N_2$ 原本的接受状态都变成普通状态。
   • 直觉: 新机器开始时，通过 $\varepsilon$-转移“猜测”要去匹配 $L(N_1)$ 还是 $L(N_2)$。如果任意一条路径成功，整个字符串就被接受。

• 情况 5: $R = R_1 \circ R_2$ (连接)
• 目标: 构造一个 NFA $N$ 来识别 $L(N_1) \circ L(N_2)$。
• 构造:

1. 将 $N_1$ 的起始状态作为新机器 $N$ 的起始状态。
2. 将 $N_2$ 的接受状态作为新机器 $N$ 的接受状态。
3. 从 $N_1$ 的所有接受状态画 $\varepsilon$-转移箭头，指向 $N_2$ 的起始状态。
4. 将 $N_1$ 原本的接受状态都变成普通状态。
   • 直觉: 机器首先必须完整地匹配一个 $L(N_1)$ 中的字符串，走到 $N_1$ 的终点，然后通过 $\varepsilon$-转移“无缝衔接”到 $N_2$ 的起点，接着必须完整地匹配一个 $L(N_2)$ 中的字符串。

• 情况 6: $R = R_1^*$ (星号)
• 目标: 构造一个 NFA $N$ 来识别 $(L(N_1))^*$。
• 构造:

1. 创建一个新的起始状态 $q_{new\_start}$，它同时也是接受状态（为了处理 0 次重复，即接受 $\varepsilon$）。
2. 创建一个新的接受状态 $q_{new\_accept}$。
3. 从 $q_{new\_start}$ 画一条 $\varepsilon$-转移到 $N_1$ 的起始状态，和一条 $\varepsilon$-转移直接到 $q_{new\_accept}$。
4. 从 $N_1$ 的所有接受状态画 $\varepsilon$-转移，一条指回 $N_1$ 的起始状态（实现循环），另一条指向 $q_{new\_accept}$（结束循环）。
5. $N_1$ 原本的起始和接受状态都变成普通状态。
   • 简化版构造:
6. 创建一个新的起始状态 $q_{new\_start}$，同时也是接受状态。
7. 从 $q_{new\_start}$ 画一条 $\varepsilon$ 边到 $N_1$ 的起始状态。
8. 从 $N_1$ 的所有接受状态画 $\varepsilon$ 边到 $q_{new\_start}$。
   • 直觉: 机器可以从头（$q_{new\_start}$）直接到尾，接受 $\varepsilon$。或者，它可以进入 $N_1$ 子模块，匹配一个 $L(N_1)$ 中的字符串，然后通过 $\varepsilon$-转移回到起点，准备再次进入 $N_1$ 匹配下一个，或者选择结束。这个循环结构允许匹配任意多次。
9. 证明完成
   • 通过为 3 种基础情况和 3 种归纳情况都提供了具体的 NFA 构造方法，我们完整地展示了如何将任何一个正则表达式转换为等价的 NFA。
   • 这个算法（通常称为 Thompson's Construction）是递归的、确定性的，保证能为任何合法的正则表达式生成一个 NFA。
   • 因此，引理 1.55 成立：任何被正则表达式描述的语言，都能被一个 NFA 识别，故它是一个正则语言。这完成了定理 1.54 "if" 部分的证明。

这个例子完整地演示了前面描述的 Thompson's Construction 算法。它严格遵循从内到外、从简单到复杂的构建顺序，将一个具体的正则表达式 $(\mathrm{ab} \cup \mathrm{a})^{*}$ 一步步地转换成一个 NFA。

分析表达式的结构树

首先，我们需要像解析一个数学公式一样，分析 $(\mathrm{ab} \cup \mathrm{a})^{*}$ 的结构：

• 最外层是星号运算 *。
• 星号内部是并运算 U。
• 并运算的左边是连接运算 ab。
• 并运算的右边是 a。
• 最底层的原子表达式是 a 和 b。

所以，构建的顺序应该是：

1. 构造 a 和 b 的 NFA。
2. 使用 a 和 b 的 NFA 构造 ab 的 NFA。
3. 我们已经有 a 的 NFA。
4. 使用 ab 和 a 的 NFA 构造 ab U a 的 NFA。
5. 最后，使用 ab U a 的 NFA 构造 (ab U a)* 的 NFA。

图 1.57 的分步详解

1. 第一行: a 和 b (基础情况)
   • 左图 (a): 对应正则表达式 a。根据基础规则 1，构造一个两状态 NFA，中间由 a 箭头连接。
   • 右图 (b): 对应正则表达式 b。同样，构造一个两状态 NFA，中间由 b 箭头连接。
   • 这是我们最小的“积木块”。
2. 第二行: ab (连接运算)
   • 目标: 构造正则表达式 ab 的 NFA。这是 a 和 b 的连接。
   • 方法: 使用连接的构造规则。
3. 取 a 的 NFA ($N_a$) 和 b 的 NFA ($N_b$)。
4. 将 $N_a$ 的接受状态通过一条 $\varepsilon$-转移箭头连接到 $N_b$ 的起始状态。
5. $N_a$ 的起始状态成为新机器的起始状态。
6. $N_b$ 的接受状态成为新机器的接受状态。
   • 图中结果: 将第一行的 a 的 NFA 的终点，通过 $\varepsilon$ 连接到 b 的 NFA 的起点，形成了一个三状态的链。这个链只接受字符串 ab。
7. 第三行: ab U a (并运算)
   • 目标: 构造 ab U a 的 NFA。
   • 子模块: 我们需要 ab 的 NFA (来自第二行) 和 a 的 NFA (来自第一行)。
   • 方法: 使用并的构造规则。
8. 创建一个新的起始状态。
9. 从新起点画两条 $\varepsilon$-转移，分别指向 ab 的 NFA 的起点和 a 的 NFA 的起点。
10. 创建一个新的接受状态。
11. 从 ab 的 NFA 的终点和 a 的 NFA 的终点画 $\varepsilon$-转移到新终点。
    • 图中结果: 一个菱形的结构。机器开始时，可以选择走上面的路径（匹配 ab）或者走下面的路径（匹配 a）。
12. 第四行: (ab U a)* (星号运算)
    • 目标: 构造 (ab U a)* 的 NFA。
    • 子模块: 我们需要 ab U a 的 NFA (来自第三行)。
    • 方法: 使用星号的构造规则。
13. 创建一个新的起始状态，它同时也是接受状态（为了匹配空字符串 $\varepsilon$）。
14. 从新起点画一条 $\varepsilon$-转移到 ab U a 的 NFA (即第三行的菱形结构) 的起点。
15. 从 ab U a 的 NFA 的终点画一条 $\varepsilon$-转移回到新起点（形成循环）。
16. (在书中的画法中，还额外有一个新的接受状态，并且从旧的接受状态和新的起始状态都有 $\varepsilon$ 边连过去，这是一种等价但更严格的画法，保证单一出口)。
    • 图中结果: 整个菱形结构被一个大的循环和出入口包裹起来。机器可以：
    • 直接从新起点到新终点（通过最外围的 $\varepsilon$ 边），接受 $\varepsilon$。
    • 进入菱形，匹配一个 ab 或 a，然后回到起点，准备下一次匹配。
    • 在任意次匹配后，从菱形的终点退出到最终的接受状态。

关于状态最少的 NFA

• 算法的产物: Thompson's Construction 生成的 NFA 有 8 个状态，并且有大量的 $\varepsilon$-转移。它虽然保证正确，但通常是冗余的。
• 语言的本质: 让我们分析一下语言 $L((ab \cup a)^*)$。它是由 ab 和 a 进行任意次数的拼接。
• 这个语言里包含了 a, aa, ab, aab, aba 等等。
• 实际上，这个语言就是所有由 a 和 b 组成，且不以 b 开头，并且没有任何两个连续的 b 的字符串的集合。或者更简单地想：它等价于所有以 a 开头的字符串，只要其中不出现 bb 子串。
• 一个更简单的等价正则表达式是 a(aba)a*。
• 更直接地看，任何由 a 和 b 组成的字符串，只要它以 a 开头，并且 b 后面必须跟着 a，似乎都可以。不，aa可以，ab可以, aba可以。其实就是所有不含 bb 子串且不以 b 开头的字符串。
• 让我们再思考一下，这个语言其实就是所有以 'a' 开头，并且任意一个 'b' 后面必须紧跟着一个 'a' 的字符串。
• 不，(ab U a)* 可以生成 a，也可以生成 ab，也可以生成 aab，aba。
• 其实 $L((ab \cup a)^*)$ 就是 $L((a(b \cup \varepsilon))^*)$。 这代表了所有由 a 和 ab 组成的字符串。这意味着所有字符串都以 a 开头，并且b前面必须有a。
• 一个更简单的想法：这个语言包含空字符串。所有非空字符串都必须以 a 开头。在 a 之后，可以有另一个 a，也可以有一个 b，但 b 之后不能再跟 b。
• 最小的等价 NFA:
• 状态0 (起始, 接受): 代表空字符串或一个合法的字符串结尾。
• 状态1 (接受): 代表刚读完一个a，也是合法的结尾。
• 从状态0读 a -> 状态1. (可以开始一个新的 a... 或者 ab... 序列)
• 从状态1读 a -> 状态1. (...aa...)
• 从状态1读 b -> 状态0. (...ab...，此时必须重新以a开头)
• 这个 NFA 似乎可行。让我们检查一下：
• 输入 a: 0 -> 1 (接受)
• 输入 ab: 0 -> 1 -> 0 (接受)
• 输入 aba: 0 -> 1 -> 0 -> 1 (接受)
• 输入 aa: 0 -> 1 -> 1 (接受)
• 输入 b: (从0无法读b) 拒绝。正确。
• 输入 bb: (无路径) 拒绝。正确。
• 所以，一个两状态的 NFA 确实可以实现。状态0（起始，接受）和状态1（接受）。从0读a到1。从1读a到1。从1读b到0。所有其他转换都到“死亡状态”。这个机器接受所有由 a 和 ab 组成的字符串，这正是 (a U ab)，也就等价于 (ab U a)。

这个例子比上一个更复杂，它组合了并、星号和多次连接。它旨在展示 Thompson's Construction 算法处理更长序列的能力，并省略了一些中间步骤以突出关键的组合过程。

分析表达式的结构树

正则表达式是 $(\mathrm{a} \cup \mathrm{b})^{*} \mathrm{aba}$。根据优先级（星号 > 连接 > 并），它的结构是：

$(((\mathrm{a} \cup \mathrm{b})^{*}) \circ \mathrm{a}) \circ \mathrm{b}) \circ \mathrm{a}$

这是一个由四个主要部分连接而成的长链：

1. 部分1: $(\mathrm{a} \cup \mathrm{b})^{*}$
2. 部分2: $\mathrm{a}$
3. 部分3: $\mathrm{b}$
4. 部分4: $\mathrm{a}$

所以，构建的顺序是：

1. 构造 a 和 b 的 NFA (基础)。
2. 使用它们构造 a U b 的 NFA (并)。
3. 使用 a U b 的 NFA 构造 (a U b)* 的 NFA (星号)。这是第一大块。
4. 构造 a, b, a 各自的 NFA (基础)。
5. 使用连接规则，将 (a U b)* 的 NFA、a 的 NFA、b 的 NFA、a 的 NFA 像串珠子一样串联起来。

图 1.59 的分步详解

1. a, b (未显示，但为基础)
   • 与上例相同，我们脑中已有 a 和 b 的两状态 NFA 作为零件。
2. a U b (第一行)
   • 目标: 构造 a U b 的 NFA。
   • 方法: 应用并的构造规则。创建一个新起点，用 $\varepsilon$-转移连接到 a 和 b 的 NFA 的起点。创建一个新终点，a 和 b 的 NFA 的终点都用 $\varepsilon$-转移连接到它。
   • 图中结果: 一个包含 6 个状态的菱形结构，与上一个例子的第三步类似。
3. (a U b)* (第二行)
   • 目标: 构造 (a U b)* 的 NFA。
   • 子模块: 使用第一行得到的 a U b 的 NFA。
   • 方法: 应用星号的构造规则。
4. 创建一个新的起始/接受状态。
5. 从新起点画 $\varepsilon$-转移到 a U b NFA 的起点。
6. 从 a U b NFA 的终点画 $\varepsilon$-转移回到新起点。
   • 图中结果: 一个大的循环结构，包裹着 a U b 的菱形。这个模块可以匹配任意由 a 和 b 组成的字符串。
7. aba (第三行)
   • 目标: 构造 aba 的 NFA。这是 a $\circ$ b $\circ$ a 的连接。
   • 方法: 应用两次连接的构造规则。
8. 取一个 a 的 NFA ($N_a$)。
9. 将其终点用 $\varepsilon$-转移连接到 b 的 NFA ($N_b$) 的起点。
10. 将 $N_b$ 的终点用 $\varepsilon$-转移连接到另一个 a 的 NFA ($N_{a'}$)。
    • 图中结果: 一个由 a 弧、$\varepsilon$ 弧、b 弧、$\varepsilon$ 弧、a 弧串起来的链条。这个模块只接受字符串 aba。
11. (a U b)*aba (第四行)
    • 目标: 构造最终的正则表达式。
    • 子模块: 第二行的 (a U b)* NFA 和第三行的 aba NFA。
    • 方法: 应用连接的构造规则。
12. 取 (a U b)* 的 NFA (我们称之为 $N_{star}$)。
13. 取 aba 的 NFA (我们称之为 $N_{aba}$)。
14. 将 $N_{star}$ 的接受状态通过一条 $\varepsilon$-转移连接到 $N_{aba}$ 的起始状态。
15. $N_{star}$ 的起始状态是新机器的起点。
16. $N_{aba}$ 的接受状态是新机器的终点。
    • 图中结果: 将第二行的整个循环结构和第三行的整个链条结构，通过一个 $\varepsilon$ 箭头“焊接”在一起。

最终 NFA 的工作流程

这个最终构造出的复杂 NFA 如何识别一个字符串，比如 aababa？

1. 字符串 aab 会在第一部分 (a U b)* 的循环中被匹配。机器可能会在循环体里走三次，分别匹配 a, a, b。
2. 匹配完 aab 后，机器到达了原 $N_{star}$ 的接受状态。
3. 通过关键的 $\varepsilon$-转移，机器“跳”到了 $N_{aba}$ 的起始状态。这个过程不消耗任何输入字符。
4. 此时，输入字符串还剩下 aba。
5. 机器在 $N_{aba}$ 子模块中，依次匹配 a, b, a。
6. 最终，机器恰好在消耗完所有输入的同时，到达了整个 NFA 的最终接受状态。
7. 因此，字符串 aababa 被接受。

这是定理 1.54 第二个方向的证明，也是更难、更具技巧性的一个。它旨在说明，任何正则语言（即任何能被 DFA 识别的语言）都可以用一个正则表达式来描述。

1. 证明的逻辑链
   • 前提: 我们有一个正则语言 $A$。
   • 根据正则语言的定义: 存在一个 DFA (确定型有限自动机) $M$，它能识别语言 $A$ (即 $L(M) = A$)。
   • 目标: 找到一个正则表达式 $R$，使得 $L(R) = A$。
   • 证明策略: 我们需要一个算法，这个算法的输入是一个 DFA，输出是一个等价的正则表达式。
2. 引入一个中间工具：GNFA
   • 直接从 DFA 转换到正则表达式在思路上比较困难。作者在这里引入了一个非常聪明的中间步骤——广义非确定型有限自动机 (Generalized Nondeterministic Finite Automaton, GNFA)。
   • 这个转换过程被分成了两步，使得每一步都更容易处理：
   • 第一步: 将输入的 DFA 转换成一个特定形式的 GNFA。这一步相对直接，主要是格式上的调整。
   • 第二步: 通过一个递归的状态消除过程，将这个 GNFA 逐步简化，直到它变成一个非常简单的 GNFA，其等价的正则表达式可以被直接读出。这是整个证明的核心和难点。
3. 什么是 GNFA？
   • 广义 (Generalized) 这个词是关键。它“广义”在什么地方？
   • 转移箭头的标签:
   • 在普通的 NFA 或 DFA 中，状态之间的转移箭头上的标签只能是一个单一的字符 (来自字母表 $\Sigma$)，或者是 $\varepsilon$。
   • 在 GNFA 中，转移箭头上的标签可以是任何一个正则表达式！
   • 工作方式:
   • 普通的 NFA 一次只“消耗”一个字符（或不消耗，对于 $\varepsilon$）。
   • GNFA 在从状态 A 移动到状态 B 时，可以一次性“消耗”掉输入字符串中的一个子串。这个子串必须是箭头标签上的正则表达式所描述的语言中的一员。
   • 例子: 如果从状态 $q_1$ 到 $q_2$ 的箭头上标签是正则表达式 (ab)*c，那么 GNFA 可以从 $q_1$ 开始，在读完输入字符串中的 ababc 这个子串后，直接到达状态 $q_2$。
4. 两步走战略的优势
   • DFA -> GNFA: 这一步是“升维”。我们把简单的、只带字符标签的 DFA，变成一个复杂的、带正则表达式标签的 GNFA。这看起来似乎把问题搞复杂了，但实际上是为了第二步做准备。在这一步，原 DFA 的字符标签 a 会被看作是正则表达式 a。
   • GNFA -> 正则表达式: 这一步是“降维”。我们通过不断地“消除状态”，把一个有 N 个状态的 GNFA 变成一个等价的、只有 N-1 个状态的 GNFA。每消除一个状态，我们就把经过它的路径信息，通过正则运算（并、连接、星号）“合并”到保留下来的状态之间的箭头的正则表达式标签上。这个过程一直持续，直到 GNFA 只剩下起始状态和接受状态。此时，从起始状态到接受状态的唯一箭头上的那个（可能非常复杂的）正则表达式，就是我们最终要找的答案。

本段详细定义了 GNFA 及其为了方便转换而规定的“特殊形式”，并说明了如何将一个普通的 DFA 转换成这种特殊形式的 GNFA。这是 DFA -> 正则表达式 转换算法的第一步。

1. GNFA 的核心特征
   • 标签是正则表达式: 这是它与 NFA 最根本的区别。NFA 的边上是单个字符或 $\varepsilon$，而 GNFA 的边上可以是任意复杂的正则表达式，如 (a|b)* 或 a(b|c)d。
   • 消耗符号块: 当 GNFA 沿着一条边从 $q_i$ 移动到 $q_j$ 时，它不是消耗一个字符，而是消耗一个“符号块”，即一个字符串。这个被消耗的字符串 $w$ 必须是边上正则表达式 $R$ 所描述的语言 $L(R)$ 的一员。
   • 非确定性: 与 NFA 类似，GNFA 也是非确定型的。这意味着对于一个输入字符串，可能有多条计算路径。例如，如果输入是 ab，一条边是 a，另一条是 ab，机器可以“猜测”走哪条路。只要存在至少一条合法的路径能让机器在消耗完整个输入后到达接受状态，该输入就被接受。
2. 图 1.61 示例解读
   • 这个 GNFA 有三个状态：$q_{start}$, $q_1$, $q_{accept}$。
   • 从 $q_{start}$ 到 $q_1$ 的边标签是 (a U b)*。这意味着机器可以消耗任意 a,b 串，从 $q_{start}$ 到达 $q_1$。
   • $q_1$ 有一个自循环，标签是 a。这意味着在 $q_1$ 时，可以消耗一个 a 然后回到 $q_1$。
   • 从 $q_1$ 到 $q_{accept}$ 的边标签是 b。这意味着必须消耗一个 b 才能从 $q_1$ 到达接受状态。
   • 这个 GNFA 接受什么语言？
   • 一个字符串要被接受，必须能从 $q_{start}$ 走到 $q_{accept}$。
   • 路径是 $q_{start} \rightarrow q_1 \rightarrow \dots \rightarrow q_1 \rightarrow q_{accept}$。
   • $q_{start} \rightarrow q_1$：消耗一个字符串 $w_1 \in L((a \cup b)^*)$。
   • $q_1 \rightarrow \dots \rightarrow q_1$：在 $q_1$ 循环 $k$ 次，消耗 $k$ 个 a，即字符串 $a^k$。
   • $q_1 \rightarrow q_{accept}$：消耗一个 b。
   • 所以，被接受的字符串的结构是 $w_1 \circ a^k \circ b$。其中 $w_1$ 是任意 a,b 串，$k \geq 0$。
   • $w_1 \circ a^k$ 的组合实际上还是一个任意的 a,b 串。
   • 所以这个 GNFA 接受的语言是所有以 b 结尾的字符串，即 $L((a \cup b)^*b)$。
3. GNFA 的“特殊形式” (Canonical Form)
   • 为了让后续的“状态消除”算法能够统一、方便地进行，我们对 GNFA 的结构做了一些严格的规定。这就像在解方程前，我们先把所有方程都整理成“标准形式”。
   • 规则 1 (起始状态): 有一个唯一的起始状态，它只出不进。即，有从它出发到所有其他状态的边，但没有任何边指向它。这确保了计算总有一个干净的起点。
   • 规则 2 (接受状态): 只有一个唯一的接受状态，它只进不出。即，有从所有其他状态指向它的边，但没有从它出发的边。这确保了计算总有一个明确的终点。并且，起始状态和接受状态不能是同一个状态。
   • 规则 3 (全连接): 除了起始和接受状态，任何两个状态 $q_i, q_j$ 之间都有一条从 $q_i$到 $q_j$ 的边（包括 $q_i$ 到自身的自循环边）。这保证了我们在进行状态消除时，总能找到需要更新的边，算法逻辑可以统一。
4. 将 DFA 转换为特殊形式的 GNFA
   • 这是转换算法的第一步，非常程序化。
   • 步骤 1 (添加新起点/终点):
   • 在原 DFA 的基础上，创建一个全新的起始状态 $q_{start\_new}$。从 $q_{start\_new}$ 画一条 $\varepsilon$-转移边到原 DFA 的起始状态。
   • 创建一个全新的接受状态 $q_{accept\_new}$。从原 DFA 的所有接受状态画 $\varepsilon$-转移边到 $q_{accept\_new}$。
   • 这样就满足了“只出不进”的起点和“只进不出”的终点规则。
   • 步骤 2 (合并多重边):
   • 在原 DFA 中，如果从状态 A 到状态 B 有多条边（例如，NFA 中可能出现），比如一条标 a，一条标 b。在 GNFA 中，我们将它们合并成一条边，其标签是原标签的并，即 a U b。
   • 步骤 3 (添加缺失边):
   • 为了满足“全连接”规则，检查任意两个状态之间是否缺少边。如果从 $q_i$ 到 $q_j$ 没有边，就添加一条，并标记为 ∅。
   • 为什么标记 ∅？因为 $L(\emptyset) = \{\}$，没有任何字符串属于这个语言，所以这条边在计算中永远不会被走到。这在逻辑上等价于“没有边”。
   • 经过这三步，任何 DFA（或 NFA）都可以被转换成一个行为完全等价的、满足特殊形式的 GNFA。

这是整个 DFA -> 正则表达式 证明的核心算法：状态消除法。它描述了一个递归过程，通过不断减少 GNFA 的状态数量，最终得到一个只含起始和接受状态的二状态 GNFA，从而直接读出等价的正则表达式。

1. 算法的总体流程 (递归)
   • 输入: 一个有 $k$ 个状态的、处于“特殊形式”的 GNFA。
   • 终止条件 (Base Case): 如果 $k=2$，那么这个 GNFA 只剩下起始状态 $q_{start}$ 和接受状态 $q_{accept}$。由于是特殊形式，它们之间只有一条从 $q_{start}$ 到 $q_{accept}$ 的边。这条边上的正则表达式 $R$ 就描述了从起点到终点的所有路径。因此，这个 $R$ 就是我们要求的最终结果。算法结束。
   • 递归步骤 (Recursive Step): 如果 $k > 2$，执行以下操作：
2. 选择: 从 GNFA 中选择一个“待消除”的状态 $q_{rip}$。这个状态不能是起始状态或接受状态。因为 $k>2$，所以这样的状态一定存在。
3. 转换: 创建一个新的、$k-1$ 个状态的 GNFA。这个新 GNFA 中不包含 $q_{rip}$。
4. 修复: 为了补偿 $q_{rip}$ 的消失，需要更新新 GNFA 中所有剩余的边的标签。
5. 递归: 对这个新的、$k-1$ 状态的 GNFA，重新调用本算法。
6. 核心操作：修复边的标签 (状态消除公式)
   • 这是整个算法最关键的部分。当我们把状态 $q_{rip}$ 从图中“撕掉”后，原来所有经过 $q_{rip}$ 的路径都断了。我们需要通过修改其他边的标签，把这些断掉的路径信息“嫁接”回去。
   • 考虑任意一对剩下的状态 $q_i$ 和 $q_j$（$q_i$ 不能是接受状态，$q_j$ 不能是起始状态）。我们要计算从 $q_i$ 到 $q_j$ 的新标签。
   • 原来的路径: 从 $q_i$ 到 $q_j$ 的路径有两种：
7. 直接路径: 不经过 $q_{rip}$，直接从 $q_i$ 到 $q_j$。这条路径由原来的边 $q_i \xrightarrow{R_4} q_j$ 上的正则表达式 $R_4$ 描述。
8. 间接路径: 必须经过 $q_{rip}$。这条路径可以分解为三步：
   • 第一步: 从 $q_i$ 到 $q_{rip}$。由边 $q_i \xrightarrow{R_1} q_{rip}$ 描述。
   • 第二步: 在 $q_{rip}$ 上“兜圈子”。$q_{rip}$ 可能有一个自循环边 $q_{rip} \xrightarrow{R_2} q_{rip}$。计算流可以在这里循环 0 次或任意多次。这个循环过程由正则表达式 $(R_2)^*$ 描述。
   • 第三步: 从 $q_{rip}$ 到 $q_j$。由边 $q_{rip} \xrightarrow{R_3} q_j$ 描述。
   • 将这三步连接起来，就构成了所有经过 $q_{rip}$ 一次（或一连串循环）的路径，由正则表达式 $(R_1)(R_2)^*(R_3)$ 描述。
   • 新标签的组合: 新的从 $q_i$到 $q_j$ 的路径，可以是原来的直接路径，或者是新的间接路径。在正则表达式中，“或者”就是并运算 $\cup$。
   • 最终公式:
   • $R_1$: 从 $q_i$ 到 $q_{rip}$ 的旧标签。
   • $R_2$: 从 $q_{rip}$ 到 $q_{rip}$ 的旧标签（自循环）。
   • $R_3$: 从 $q_{rip}$ 到 $q_j$ 的旧标签。
   • $R_4$: 从 $q_i$ 到 $q_j$ 的旧标签。
   • 重要: 这个更新公式需要对所有可能的 $q_i, q_j$ 组合（$q_i \neq q_{accept}, q_j \neq q_{start}$）都执行一遍，包括 $q_i = q_j$ 的情况（即更新自循环边的标签）。
9. 图 1.62 和 1.63 的解读
   • 图 1.62: 宏观地展示了整个流程。从一个多状态的 DFA 开始，首先转换为一个 $k$ 状态的 GNFA (这里 $k=3+2=5$，但图中简化了，假设为4)，然后消除一个状态变成 $k-1=3$ 状态的 GNFA，最后再消除一个状态，变成 $k-2=2$ 状态的 GNFA。在这个最终的 2 状态 GNFA 中，从起点到终点的边上就是最终的正则表达式。
   • 图 1.63: 微观地展示了单次状态消除的核心操作。它直观地画出了公式的来源：从 $q_i$ 到 $q_j$ 的新路径，等于老路径 $R_4$ 加上那条绕道 $q_{rip}$ 的新路径。

这一部分提供了 GNFA 的严格数学定义，并形式化地描述了 GNFA 是如何“接受”一个字符串的。这是将前面直观的描述转化为严谨的数学语言的关键步骤。

1. GNFA 的形式化五元组定义
   • 与 DFA 和 NFA 类似，GNFA 也被定义为一个五元组 $\left(Q, \Sigma, \delta, q_{\text {start }}, q_{\text {accept }}\right)$。我们来逐项分析：
   • 1. $Q$ (有限状态集): 与 NFA/DFA 相同，是一组有限的状态。
   • 2. $\Sigma$ (输入字母表): 与 NFA/DFA 相同，是构成字符串的基本字符集。
   • 3. $\delta$ (转移函数): 这是与 NFA/DFA 核心区别所在。
   • 函数签名: $\delta:\left(Q-\left\{q_{\text {accept }}\right\}\right) \times\left(Q-\left\{q_{\text {start }}\right\}\right) \longrightarrow \mathcal{R}$
   • 输入 (Domain): $\left(Q-\left\{q_{\text {accept }}\right\}\right) \times\left(Q-\left\{q_{\text {start }}\right\}\right)$
   • 这是一个笛卡尔积，代表一个“状态对” $(q_{from}, q_{to})$。
   • $q_{from}$ 可以是任何状态，但不能是接受状态 ($q_{\text {accept }}$)。这对应了“接受状态只进不出”的规则。
   • $q_{to}$ 可以是任何状态，但不能是起始状态 ($q_{\text {start }}$)。这对应了“起始状态只出不进”的规则。
   • 这个定义域精确地编码了我们对“特殊形式” GNFA 的结构要求。
   • 输出 (Range): $\mathcal{R}$
   • $\mathcal{R}$ 代表了在字母表 $\Sigma$ 上所有可能的正则表达式的集合。
   • 这意味着，$\delta$ 函数的返回值不是一个状态或一个状态集，而是一个正则表达式。
   • 含义: $\delta(q_i, q_j) = R$ 表示从状态 $q_i$ 到 $q_j$ 的边的标签是正则表达式 $R$。
   • 4. $q_{start}$ (起始状态): 一个特殊指定的起始状态。
   • 5. $q_{accept}$ (接受状态): 一个特殊指定的、唯一的接受状态。
2. GNFA 的接受条件 (形式化定义)
   • 这段定义了 GNFA 如何工作。一个字符串 $w$ 被 GNFA 接受，需要满足以下所有条件：
   • 1. 字符串的分解: 字符串 $w$ 必须能够被分解成一连串的子字符串 $w_1, w_2, \dots, w_k$，即 $w = w_1w_2\dots w_k$。注意这里的 $w_i$ 不是单个字符，而是字符串。
   • 2. 状态路径的存在性: 必须存在一个状态序列 $q_0, q_1, \dots, q_k$：
   • 这个路径的起点必须是起始状态 ($q_0 = q_{start}$)。
   • 这个路径的终点必须是接受状态 ($q_k = q_{accept}$)。
   • 3. 每一步的合法性: 对于路径中的每一步（从 $q_{i-1}$ 到 $q_i$），对应的字符串块 $w_i$ 必须属于连接这两个状态的边上的正则表达式 $R_i = \delta(q_{i-1}, q_i)$ 所描述的语言。即，$w_i \in L(R_i)$。
   • 总结: 如果我们能找到一种方法，把输入字符串 $w$ 切割成几段，并且能找到一条从起始状态到接受状态的状态路径，使得切割的每一段字符串都能被路径上对应步骤的边的正则表达式所匹配，那么字符串 $w$ 就被接受。

这一部分形式化地定义了前面讨论的状态消除算法，并将其包装成一个名为 CONVERT 的递归过程。

1. 算法的起点
   • 证明的第一步（在调用 CONVERT 之前）是将给定的 DFA $M$ 转换成一个满足“特殊形式”的 GNFA $G$。这个预处理步骤我们已经讨论过，它确保了我们交给 CONVERT 的输入是标准化的。
2. CONVERT(G) 过程详解
   • 这是一个递归算法，其设计思想是“分而治之”(Divide and Conquer)。
   • 输入: 一个 GNFA $G$。
   • 输出: 一个与 $G$ 等价的正则表达式。

• 步骤 1: 获取状态数
• 设 k 为 G 的状态数。
• $k$ 的大小是驱动递归的关键变量。

• 步骤 2: 终止条件 (Base Case)
• 如果 k=2，... 返回表达式 R。
• 这是递归的出口。当 GNFA 被简化到只剩下起始状态和接受状态时，我们不再需要递归。
• 由于 GNFA 是特殊形式，这两个状态之间只有一条从起点到终点的边。
• 这条边上的正则表达式 $R$ 自然地描述了从头到尾所有可能的路径（因为已经没有中间状态可以绕路了）。所以这个 $R$ 就是答案。

• 步骤 3: 递归步骤 (Recursive Step)
• 如果 k > 2，...
• 这是算法的核心，对应“分治”中的“治”。
• a. 选择一个状态 $q_{rip}$:
• 从除了起始和接受状态之外的中间状态中，随便选一个出来，作为本次要“撕掉”的目标。
• b. 构建简化的 $G'$:
• 定义一个新的 GNFA $G'$，它的状态集 $Q'$ 就是原来的状态集 $Q$ 减去 $q_{rip}$。所以 $G'$ 的状态数是 $k-1$。
• $G'$ 的起点、终点、字母表都和 $G$ 一样。
• c. 计算新的转移函数 $\delta'$ (核心公式):
• 这是最关键的一步：为 $G'$ 中的每一条边计算新的正则表达式标签。
• 对于任何一对状态 $(q_i, q_j)$ (其中 $q_i$ 不是终点, $q_j$ 不是起点)，新的标签 $\delta'(q_i, q_j)$ 由以下公式给出：

• 这里的 $R_1, R_2, R_3, R_4$ 都是从旧的 GNFA $G$ 的转移函数 $\delta$ 中取出的值：
• $R_1 = \delta(q_i, q_{rip})$ (从 $q_i$ 到 $q_{rip}$ 的路径)
• $R_2 = \delta(q_{rip}, q_{rip})$ (在 $q_{rip}$ 的自循环路径)
• $R_3 = \delta(q_{rip}, q_j)$ (从 $q_{rip}$到 $q_j$ 的路径)
• $R_4 = \delta(q_i, q_j)$ (从 $q_i$ 到 $q_j$ 的不经过 $q_{rip}$ 的直接路径)
• 这个公式的含义我们前面已经深入讨论过：它将所有经过 $q_{rip}$ 的路径信息，通过正则运算，编码并合并到了不经过 $q_{rip}$ 的路径上。

• 步骤 4: 递归调用
• 计算 Convert(G') 并返回此值。
• 现在我们有了一个新的、状态数减一的 GNFA $G'$。我们把这个更小的问题，扔回给 CONVERT 函数自己去解决。
• 因为每次递归调用，问题的规模（状态数 $k$）都在减小，所以这个递归过程最终必然会达到 $k=2$ 的终止条件，从而保证算法会结束。

这是对 CONVERT 算法正确性的形式化证明，它使用了数学归纳法。证明的核心是论证，每一步状态消除操作所产生的新的、更小的 GNFA $G'$，与原来的 GNFA $G$ 在语言识别能力上是完全等价的。

证明结构：对状态数 k 进行归纳

1. 断言 (Claim): 我们要证明的命题是 “对于任何有 $k$ 个状态的 GNFA $G$，CONVERT(G) 返回的正则表达式 $R$ 满足 $L(R) = L(G)$”。
2. 基础情况 (Base Case): k = 2
   • 论述: 当一个 GNFA 只有 2 个状态时，它必然只包含起始状态 $q_{start}$ 和接受状态 $q_{accept}$。根据其“特殊形式”，从 $q_{start}$ 到 $q_{accept}$ 有且只有一条边，设其标签为正则表达式 $R$。
   • 根据 GNFA 的接受定义，一个字符串 $w$ 被这个二状态 GNFA 接受，当且仅当 $w$ 可以被分解成一段 $w_1$，使得 $w_1 \in L(R)$，并且路径是 $q_{start} \rightarrow q_{accept}$。由于 $w$ 只能被分解成它自身，所以这意味着 $w \in L(R)$。
   • 因此，这个 GNFA 接受的语言就是 $L(R)$。
   • CONVERT 算法在 $k=2$ 时，正是返回了这个正则表达式 $R$。
   • 结论: 在 $k=2$ 的情况下，断言成立。
3. 归纳步骤 (Inductive Step)
   • 归纳假设 (Inductive Hypothesis): 假设断言对于所有状态数为 $k-1$ 的 GNFA 都成立。也就是说，我们相信 CONVERT 算法对于 $k-1$ 个状态的 GNFA 能够给出正确的结果。
   • 目标: 在这个假设下，证明断言对于状态数为 $k$ 的 GNFA 也成立。
   • 核心论点: 我们需要证明，CONVERT 算法中从 $k$ 状态的 $G$ 构造出的 $k-1$ 状态的 $G'$，与 $G$ 是等价的，即 $L(G) = L(G')$。
   • 如果能证明这一点，那么逻辑链就是：
4. $L(G) = L(G')$ (我们将要证明的)。
5. CONVERT(G) 的执行过程是返回 CONVERT(G') 的结果。
6. 根据归纳假设，CONVERT(G') 返回的正则表达式 $R$ 与 $G'$ 等价，即 $L(R) = L(G')$。
7. 综合 1 和 3，我们得到 $L(R) = L(G)$。
8. 这就证明了 CONVERT(G) 返回了与 $G$ 等价的正则表达式。断言对于 $k$ 成立。
9. 证明 $L(G) = L(G')$
   • 这是一个集合相等的证明，需要证明两个方向：$L(G) \subseteq L(G')$ 和 $L(G') \subseteq L(G)$。
   • 方向一: 证明如果 $w \in L(G)$，那么 $w \in L(G')$
   • 假设 $w$ 被 $G$ 接受。这意味着在 $G$ 中存在一条接受路径 $q_{start}, q_1, \dots, q_{accept}$，以及对 $w$ 的一个切分 $w_1, \dots, w_m$。
   • 情况 A: 接受路径中不包含被移除的状态 $q_{rip}$
   • 那么这条路径在 $G'$ 中也完全存在。
   • 路径中每一步 $q_i \rightarrow q_j$ 对应的边，在 $G$ 中的标签是 $R_4 = \delta(q_i, q_j)$。在 $G'$ 中，新标签是 $R_{new} = \dots \cup R_4$。
   • 因为 $L(R_4) \subseteq L(R_{new})$，所以原来合法的每一步在 $G'$ 中也仍然合法。
   • 因此，$G'$ 也接受 $w$。
   • 情况 B: 接受路径中包含了 $q_{rip}$
   • 路径看起来像 $\dots, q_i, q_{rip}, \dots, q_{rip}, q_j, \dots$。
   • 考虑任何一段从 $q_i$ 进入 $q_{rip}$，在 $q_{rip}$ 可能自循环若干次，然后从 $q_{rip}$ 离开到 $q_j$ 的子路径。
   • 这段子路径消耗的输入子串，正好是由正则表达式 $(R_1)(R_2)^*(R_3)$ 描述的。
   • 在 $G'$ 中，我们用一条从 $q_i$ 到 $q_j$ 的新边取代了这段子路径。这条新边的标签 $R_{new}$ 通过 $\cup$ 运算包含了 $(R_1)(R_2)^*(R_3)$。
   • 因此，原来在 $G$ 中需要经过 $q_{rip}$ 的多步跳转，在 $G'$ 中可以被一步等价地完成。
   • 通过将 $G$ 中所有经过 $q_{rip}$ 的子路径都替换成 $G'$ 中的单步跳转，我们可以为 $w$ 构造出一条在 $G'$ 中的接受路径。
   • 因此，$G'$ 也接受 $w$。
   • 方向二: 证明如果 $w \in L(G')$，那么 $w \in L(G)$
   • 这个方向更直接。假设 $w$ 被 $G'$ 接受。这意味着在 $G'$ 中存在一条接受路径。
   • 考虑这条路径中的任意一步，从 $q_i$ 到 $q_j$，消耗了子串 $w_{sub}$。
   • $w_{sub}$ 必须属于新标签 $R_{new} = (R_1)(R_2)^*(R_3) \cup (R_4)$。
   • 如果 $w_{sub} \in L(R_4)$: 那么在 $G$ 中，我们可以直接通过 $q_i \xrightarrow{R_4} q_j$ 这条旧的边来完成这一步。
   • 如果 $w_{sub} \in L((R_1)(R_2)^*(R_3))$: 那么在 $G$ 中，我们可以通过 $q_i \xrightarrow{R_1} q_{rip} \xrightarrow{(R_2)^*} \dots \xrightarrow{R_3} q_j$ 这一系列的跳转来消耗掉 $w_{sub}$。
   • 这意味着，$G'$ 中的每一步跳转，都可以在 $G$ 中被模拟出来（或者直接走，或者绕道 $q_{rip}$）。
   • 因此，我们可以在 $G$ 中为 $w$ 构造出一条接受路径。$w$ 也被 $G$ 接受。
   • 结论: 既然两个方向都成立，那么 $L(G) = L(G')$。
10. 最终结论
    • 通过数学归纳法，我们证明了 CONVERT(G) 对于任何状态数的 GNFA $G$ 都是正确的。
    • 这完成了对断言 1.65 的证明。
    • 断言 1.65 的成立直接保证了引理 1.60 的正确性（因为我们可以将任何 DFA 转换成 GNFA，然后调用 CONVERT）。
    • 引理 1.60（DFA -> RE）和之前的引理 1.55（RE -> NFA）共同完成了对定理 1.54 的双向证明。

这个例子完整地演示了从 DFA 到正则表达式的转换算法。

第一步：分析原始 DFA (图 1.67(a))

• 状态: 状态1 (起始), 状态2 (接受)。
• 转换:
• 在状态1，读 a -> 状态1 (自循环)。
• 在状态1，读 b -> 状态2。
• 在状态2，读 a 或 b -> 状态2 (自循环)。
• 语言: 这个 DFA 接受什么语言？
• 必须读到一个 b 才能从状态1到达状态2。
• 一旦到达状态2，就永远不会离开，所以之后可以跟任意 a 或 b 的序列。
• 在读到第一个 b 之前，可以在状态1上读任意数量的 a。
• 所以，语言是：以任意数量的 a 开头，然后跟一个 b，然后跟任意由 a,b 组成的字符串。
• 用正则表达式直观地描述就是：ab(a U b)。
• 我们的目标是通过算法推导出这个或一个等价的正则表达式。

第二步：转换为特殊形式的 GNFA (图 1.67(b))

1. 添加新起点和终点:
   • 创建一个新起始状态 s。
   • 创建一个新接受状态 a (这里用 a 表示 accept，不是字母 a)。
   • 添加 $\varepsilon$ 边: $s \xrightarrow{\varepsilon} 1$ 和 $2 \xrightarrow{\varepsilon} a$。
2. 合并/转换标签:
   • 原 DFA 的边被转换成 GNFA 的边。
   • $1 \xrightarrow{a} 1$ 变为 $1 \xrightarrow{a} 1$。
   • $1 \xrightarrow{b} 2$ 变为 $1 \xrightarrow{b} 2$。
   • $2$ 上的自循环，原来是两条边（一条 a，一条 b），被合并成一条边，标签为正则表达式 a U b。即 $2 \xrightarrow{a \cup b} 2$。
3. 添加缺失边:
   • 图中为了简洁，省略了所有标签为 ∅ 的边。例如，从 s 到 2，从 1 到 a 等，都应该有一条 ∅ 边。我们心里知道它们存在就行。

第三步：第一次状态消除，移除状态 2 (图 1.67(c))

• 目标: 移除状态 2。
• 需要更新的边: 状态 2 被移除后，剩下 s, 1, a。我们需要检查所有状态对之间的边并更新。
• s 到 1? 不经过 2，不变。
• 1 到 1? 不经过 2，不变。
• s 到 a?
• 1 到 a?
• ... 实际上，因为 2 是一个“汇点”（只进不出，除了到新终点 a），它只影响指向它的状态到它指向的状态的路径。即，从 1 到 a 的路径。
• 计算从 1 到 a 的新标签:
• 我们使用状态消除公式: $R_{new} = (R_1)(R_2)^*(R_3) \cup (R_4)$。
• $q_i = 1$, $q_j = a$, $q_{rip} = 2$。
• 在图(b)中查找旧标签：
• $R_1 = \delta(1, 2) = b$。
• $R_2 = \delta(2, 2) = a \cup b$。
• $R_3 = \delta(2, a) = \varepsilon$。
• $R_4 = \delta(1, a) = \emptyset$ (因为原来没有直达的边)。
• 代入公式:

$R_{new} = (b)(a \cup b)^*(\varepsilon) \cup (\emptyset)$

• 简化:
• $(a \cup b)^*(\varepsilon) = (a \cup b)^*$ (任何东西连接 $\varepsilon$ 都不变)。
• $(b)(a \cup b)^*$。
• $\cup (\emptyset)$ (与空集取并集不变)。
• 最终结果是: $b(a \cup b)^*$。
• 更新图: 在 (c) 中，我们看到从 1到 a 的边标签被更新为 $b(a \cup b)^*$。其他相关边不变。

第四步：第二次状态消除，移除状态 1 (图 1.67(d))

• 目标: 移除状态 1。
• 剩下状态: s, a。
• 需要更新的边: 只有从 s 到 a 这一条。
• 计算从 s 到 a 的新标签:
• $q_i = s$, $q_j = a$, $q_{rip} = 1$。
• 在图(c)中查找旧标签：
• $R_1 = \delta(s, 1) = \varepsilon$。
• $R_2 = \delta(1, 1) = a$。
• $R_3 = \delta(1, a) = b(a \cup b)^*$。
• $R_4 = \delta(s, a) = \emptyset$ (原来没有直达的边)。
• 代入公式:

$R_{new} = (\varepsilon)(a)^*(b(a \cup b)^*) \cup (\emptyset)$

• 简化:
• $(\varepsilon)(a)^* = a^*$。
• $a^*(b(a \cup b)^*)$。
• $\cup (\emptyset)$ 不变。
• 最终结果是: $a^*b(a \cup b)^*$。
• 更新图: 在 (d) 中，我们看到 s 和 a 之间只剩下一条边，其标签就是我们计算出的结果。

第五步：算法终止

• 现在 GNFA 只有 2 个状态 ($k=2$)。算法终止。
• 返回从起始状态到接受状态的边的标签。
• 最终正则表达式: $a^*b(a \cup b)^*$。
• 这与我们最初凭直觉分析 DFA 得出的语言描述完全一致！

这个例子比上一个更进了一步，从一个三状态的 DFA 开始，需要消除更多的中间状态，从而导致更复杂的正则表达式运算。

第一步：分析原始 DFA (图 1.69(a))

• 状态: 状态1 (起始), 状态2, 状态3 (接受)。
• 语言: 这个 DFA 接受什么语言？
• 它接受空字符串 $\varepsilon$ 吗？不，因为起始状态1不是接受状态。
• 要到达接受状态3，必须经过状态2。
• 路径 $1 \xrightarrow{a} 2 \xrightarrow{a} 3$ 接受 aa。
• 路径 $1 \xrightarrow{a} 2 \xrightarrow{b} 2 \xrightarrow{a} 3$ 接受 aba。
• 路径 $1 \xrightarrow{b} 1 \xrightarrow{a} 2 \xrightarrow{a} 3$ 接受 baa。
• 核心特征: 必须以一个 a 结尾才能从状态2跳到状态3。在状态2可以有任意 b 的循环。在状态1可以有任意 b 的循环。
• 直观描述: 任意数量的b（可能没有）和a交错，但a不能连续出现，后面可以跟任意数量的b，最后必须以a结尾。不对，再分析。
• 任何被接受的串，必须以 a 结尾。在 a 之前，是从状态1出发，经过一系列转换到达状态2。
• 从状态1到状态2，路径可以是：$1 \xrightarrow{a} 2$ (消耗a)，或者 $1 \xrightarrow{b} 1 \xrightarrow{a} 2$ (消耗ba)，或者 $1 \xrightarrow{a} 2 \xrightarrow{b} 2$ (消耗ab后在状态2)。
• 让我们用更简单的方式思考：所有被接受的字符串都必须以 a 结尾。最后一个 a 之前的字符串必须能把机器带到状态2。什么样的字符串能把机器带到状态2？
• 任意数量 b 后跟一个 a (b*a)。
• 或者，到了状态2后，可以跟任意数量的 b，然后再跟一个 a 到状态1，再想办法回来... 这个思路太复杂了。
• 让我们相信算法，看它能推导出什么。

第二步：转换为 GNFA (图 1.69(b))

• 这是一个 5 状态的 GNFA。
• 添加新起点 s 和新终点 a。
• 添加 $\varepsilon$ 边: $s \xrightarrow{\varepsilon} 1$, $3 \xrightarrow{\varepsilon} a$。
• 原 DFA 的边被照搬过来，标签视为正则表达式。
• 所有缺失的边都被隐式地认为是 ∅。

第三步：消除状态 3 (图 1.69(c))

• 选择: 消除状态 3。
• 分析: 状态 3 是一个“终极汇点”，没有出边。因此，消除它只会影响从其他状态到新终点 a 的路径。
• 计算从 2 到 a 的新标签:
• $q_i=2, q_j=a, q_{rip}=3$。
• $R_1 = \delta(2,3) = a$。
• $R_2 = \delta(3,3) = \emptyset$ (状态3没有自循环)。
• $R_3 = \delta(3,a) = \varepsilon$。
• $R_4 = \delta(2,a) = \emptyset$。
• $R_{new} = (a)(\emptyset)^*(\varepsilon) \cup \emptyset = a\varepsilon\varepsilon \cup \emptyset = a$。
• 结果: 从 2 到 a 的新边标签是 a。其他边不受影响。

第四步：消除状态 2 (图 1.69(d))

• 选择: 消除状态 2。
• 分析: 状态 2 是一个核心中转站。它的消除会影响 1->1, 1->a 的边。
• 计算从 1 到 1 的新标签 (更新自循环):
• $q_i=1, q_j=1, q_{rip}=2$。
• $R_1 = \delta(1,2) = a$ (在图c中查找)。
• $R_2 = \delta(2,2) = b$。
• $R_3 = \delta(2,1) = a$。
• $R_4 = \delta(1,1) = b$。
• $R_{new} = (a)(b)^*(a) \cup (b) = ab^*a \cup b$。
• 结果: 1 的自循环标签变为 $b \cup ab^*a$。
• 计算从 1 到 a 的新标签:
• $q_i=1, q_j=a, q_{rip}=2$。
• $R_1 = \delta(1,2) = a$。
• $R_2 = \delta(2,2) = b$。
• $R_3 = \delta(2,a) = a$。
• $R_4 = \delta(1,a) = \emptyset$。
• $R_{new} = (a)(b)^*(a) \cup \emptyset = ab^*a$。
• 结果: 从 1 到 a 的边标签变为 $ab^*a$。

第五步：消除状态 1 (图 1.69(e))

• 选择: 消除状态 1。
• 剩下: s, a。
• 计算从 s 到 a 的新标签:
• $q_i=s, q_j=a, q_{rip}=1$。
• $R_1 = \delta(s,1) = \varepsilon$ (在图d中查找)。
• $R_2 = \delta(1,1) = b \cup ab^*a$。
• $R_3 = \delta(1,a) = ab^*a$。
• $R_4 = \delta(s,a) = \emptyset$。
• $R_{new} = (\varepsilon)(b \cup ab^*a)^*(ab^*a) \cup \emptyset$。
• 简化: 最终结果是 $(b \cup ab^*a)^*(ab^*a)$。

最终结果分析

• 最终正则表达式: $(b \cup ab^*a)^*(ab^*a)$。
• 它描述的语言:
• 后缀: 字符串必须以 ab^*a 结尾。
• ab^a 能产生什么？ aa (当 b 是 $\varepsilon$), aba, abba, abbba, ...
• 前缀: 在这个后缀之前，可以有 0 个或多个由 b 或者 ab^*a 组成的块。
• 让我们验证几个字符串：
• aa: 前缀为空，后缀为 aa。匹配。
• aba: 前缀为空，后缀为 aba。匹配。
• baa: 前缀为 b，后缀为 aa。匹配。
• babaa: 前缀 b，后缀 aba。
• 这个表达式完美地描述了原始 DFA 的行为，尽管它的形式非常复杂，凭直觉很难直接写出来。