1 COMS 3261 讲义 6B: NFA 和正则表达式练习题解答

这份文档是哥伦比亚大学计算机科学理论课程（COMS W3261）的讲义解答，具体来说是关于非确定性有限自动机 (NFA) 和正则表达式 (Regular Expression) 的练习题解答。文档由 Ziheng Huang 和 Kiru Arjunan 编写，并感谢了 2018 年的助教 Cindy Wang 的贡献。这份材料适用于 2024 年秋季学期。它旨在帮助学生理解和掌握 NFA 和正则表达式的核心概念，以及它们之间的转换方法。

这个问题要求我们构造一个非确定性有限自动机 (NFA)，该 NFA 能够识别所有包含子串 "101" 的二进制字符串。

NFA 的核心思想是“猜测和验证”。对于这个问题，NFA 需要“猜测”子串 "101" 何时开始，然后“验证”接下来的三个字符是否确实是 "101"。

1. 起始状态 $q_0$：这是自动机的起点。在看到 "101" 子串之前，任何字符（0 或 1）的出现都只是“等待”阶段。因此，在 $q_0$ 状态，我们设置一个自循环，无论输入是 0 还是 1，状态都保持在 $q_0$。这表示 NFA 正在读取字符串的开头部分，但还没有找到 "101" 的迹象。
2. 检测到 '1'：当处于 $q_0$ 状态时，如果读入一个 '1'，NFA 会进行“猜测”。它有两个选择：
   • 选择一（留在 $q_0$）：它猜测这个 '1' 不是 "101" 子串的开始，于是继续停留在 $q_0$ 状态，等待下一个可能的 "101" 的开头。
   • 选择二（进入 $q_1$）：它猜测这个 '1' 可能是 "101" 子串的开始。于是，它从 $q_0$ 转移到新状态 $q_1$。
3. 检测到 '0'：现在假设 NFA 处于 $q_1$ 状态（因为它刚刚看到了一个 '1'）。如果下一个输入是 '0'，这符合 "101" 模式的第二个字符。于是，NFA 从 $q_1$ 转移到状态 $q_2$。
4. 检测到 '1' (完成)：如果 NFA 处于 $q_2$ 状态（意味着它已经看到了 "10"），并且下一个输入是 '1'，那么 "101" 子串就完整地出现了。此时，NFA 从 $q_2$ 转移到状态 $q_3$。
5. 接受状态 $q_3$：状态 $q_3$ 是一个接受状态。一旦进入这个状态，就意味着字符串中已经成功找到了 "101" 这个子串。由于题目要求是“包含” "101"，所以一旦找到，无论后面跟着什么字符，该字符串都应该被接受。因此，在 $q_3$ 状态，我们设置一个自循环，对于任何输入（0 或 1），状态都保持在 $q_3$。
6. 失败路径：如果猜测失败了怎么办？例如，在 $q_1$ 状态（已看到 '1'）时，如果下一个输入不是 '0' 而是 '1'，那么 "10" 的模式就断了。在 NFA 中，如果没有为某个输入定义转移，那么这条计算路径就会“死亡”。这正是 NFA 的便利之处，我们只需要关心成功路径即可。

综上所述，构造出的 NFA 如下图所示：

• $q_0$ 是起始状态。
• $q_0$ 上有一个指向自身的环，标签为 0, 1，表示在找到 "101" 的第一个 '1' 之前，可以消耗任意数量的 0 和 1。
• 从 $q_0$ 到 $q_1$ 有一条标签为 1 的边，代表猜测 "101" 的开始。
• 从 $q_1$ 到 $q_2$ 有一条标签为 0 的边。
• 从 $q_2$ 到 $q_3$ 有一条标签为 1 的边。
• $q_3$ 是接受状态。
• $q_3$ 上有一个指向自身的环，标签为 0, 1，表示一旦找到 "101"，后面可以跟任意字符。

这个问题要求我们构造一个 NFA，它接受的语言 $L$ 包含两类字符串：要么字符串中恰好有两个 0，要么字符串中有偶数个 1。

这里的关键词是“或”，这强烈暗示了我们可以分别构造识别这两个子语言的自动机，然后用并集操作将它们组合起来。NFA 的一个巨大优势就是可以轻松地实现并集操作。

第一部分：构造识别“恰好有两个 0”的 NFA ($N_1$)

我们需要一个计数器来记录 0 的数量。

1. 状态 $c_0$：起始状态，表示到目前为止有 0 个 0。在这个状态下，可以读取任意数量的 1，状态不变。如果读到 0，就转移到下一个状态。
2. 状态 $c_1$：表示到目前为止有 1 个 0。同样，可以读取任意数量的 1 而状态不变。如果读到第二个 0，就转移到下一个状态。
3. 状态 $c_2$：表示到目前为止恰好有两个 0。这是一个接受状态。在此之后，不能再出现 0，否则 0 的数量就超过 2 了。所以，这个状态只允许读取 1，并且状态保持不变。

这个子自动机 ($c_0, c_1, c_2$) 是一个 DFA。

第二部分：构造识别“偶数个 1”的 NFA ($N_2$)

我们需要一个计数器来记录 1 的奇偶性。

1. 状态 $p_0$：起始状态，表示到目前为止有偶数个 1（0 是偶数）。这是一个接受状态。如果读到 0，1 的奇偶性不变，所以状态不变。如果读到 1，1 的数量变为奇数，转移到下一个状态。
2. 状态 $p_1$：表示到目前为止有奇数个 1。这不是一个接受状态。如果读到 0，状态不变。如果读到 1，1 的数量变为偶数，转移回 $p_0$。

这个子自动机 ($p_0, p_1$) 也是一个 DFA。

第三部分：组合 $N_1$ 和 $N_2$ 得到最终的 NFA

并集的构造方法是：

1. 创建一个新的起始状态 $q_0$。
2. 从新的起始状态 $q_0$ 添加 $\epsilon$-转移（空转移）到原来两个自动机的起始状态，即 $c_0$ 和 $p_0$。

这样，当 NFA 开始处理一个字符串时，它会立即“猜测”这个字符串应该满足哪个条件：

• 如果它猜测字符串有“恰好两个 0”，它就会沿着 $\epsilon$-转移进入 $c_0$ 开始计算。
• 如果它猜测字符串有“偶数个 1”，它就会沿着另一条 $\epsilon$-转移进入 $p_0$ 开始计算。

只要最终至少有一条计算路径停在接受状态（$c_2$ 或 $p_0$），整个字符串就被接受。

最终的 NFA 结构如下：

• 新起始状态 $q_0$。
• 从 $q_0$ 到 $c_0$ 有一条 $\epsilon$-转移。
• 从 $q_0$ 到 $p_0$ 有一条 $\epsilon$-转移。
• 上半部分（来自 $N_1$）：
• $c_0 \xrightarrow{1} c_0$, $c_0 \xrightarrow{0} c_1$
• $c_1 \xrightarrow{1} c_1$, $c_1 \xrightarrow{0} c_2$
• $c_2 \xrightarrow{1} c_2$
• $c_2$ 是接受状态。
• 下半部分（来自 $N_2$）：
• $p_0 \xrightarrow{0} p_0$, $p_0 \xrightarrow{1} p_1$
• $p_1 \xrightarrow{0} p_1$, $p_1 \xrightarrow{1} p_0$
• $p_0$ 是接受状态。

这个问题展示了一个非常简单的 NFA，并询问它能识别哪种语言。

1. 分析 NFA 结构:
   • 该 NFA 只有一个状态，$q_0$。
   • $q_0$ 是起始状态（由指向它的箭头指示）。
   • $q_0$ 不是一个接受状态（它没有用双圈表示）。
   • $q_0$ 上有一个自循环，标签为 '0'。这意味着当 NFA 处于 $q_0$ 状态时，如果读入一个 '0'，它会回到 $q_0$。
   • 没有为输入 '1' 定义任何转移。
2. 寻找接受路径:
   • 根据有限自动机的定义，一个字符串被接受，当且仅当在读完整个字符串后，自动机至少存在一条计算路径，使其最终停在一个接受状态上。
   • 在这个 NFA 中，唯一的状态 $q_0$ 不是接受状态。事实上，这个 NFA 根本没有接受状态。
   • 因此，无论输入什么字符串（包括空字符串 $\epsilon$），计算路径的终点（必然是 $q_0$）永远不会是一个接受状态。
   • 例如，对于字符串 "00"：$q_0 \xrightarrow{0} q_0 \xrightarrow{0} q_0$。结束于 $q_0$，不是接受状态，拒绝。
   • 对于字符串 $\epsilon$：停在起始状态 $q_0$，不是接受状态，拒绝。
   • 对于字符串 "1"：从 $q_0$ 开始，没有为 '1' 定义的转移，计算路径死亡，拒绝。
3. 结论:
   • 由于没有任何字符串能够使这个 NFA 停在接受状态，所以它不接受任何字符串。
   • 不包含任何字符串的语言被称为空语言，用符号 $\emptyset$ 表示。

这个问题展示了另一个简单的 NFA，并询问它识别的语言。

1. 分析 NFA 结构:
   • 该 NFA 只有一个状态，$q_0$。
   • $q_0$ 是起始状态（由指向它的箭头指示）。
   • $q_0$ 是一个接受状态（由双圈表示）。
   • 这个 NFA 没有定义任何转移。从 $q_0$ 出发，无论输入是 '0' 还是 '1'，都没有对应的转移箭头。
2. 寻找接受路径:
   • 情况一：输入为空字符串 $\epsilon$
   • 根据定义，处理空字符串 $\epsilon$ 意味着自动机从起始状态开始，不消耗任何输入。
   • 因此，当输入为 $\epsilon$ 时，自动机停留在其起始状态 $q_0$。
   • 由于 $q_0$ 恰好是一个接受状态，所以空字符串 $\epsilon$ 被接受。
   • 情况二：输入为任何非空字符串 (长度 > 0)
   • 例如，考虑字符串 "0"。计算从起始状态 $q_0$ 开始。
   • 当自动机尝试读取第一个字符 '0' 时，它发现没有从 $q_0$ 出发，输入为 '0' 的转移。
   • 此时，这条计算路径“死亡”。
   • 对于任何以 '0' 或 '1' 开头的字符串，其计算路径都会在第一步死亡。
   • 由于没有计算路径能够在读完非空字符串后停留在任何状态（更不用说接受状态了），所以所有长度大于 0 的字符串都被拒绝。
3. 结论:
   • 这个 NFA 唯一能接受的字符串就是空字符串 $\epsilon$。
   • 因此，它识别的语言是只包含空字符串的语言，用集合表示为 $\{\epsilon\}$。
4. 与前一题的对比:
   • 解答中特意强调 $\emptyset \neq \{\epsilon\}$。
   • 前一个 NFA (2a) 识别空语言 $\emptyset$，这是一个不包含任何元素的集合。
   • 当前的 NFA (2b) 识别语言 $\{\epsilon\}$，这是一个包含一个元素（即空字符串）的集合。
   • 这是计算理论中一个非常基础且重要的区别。

这个问题要求我们将一个给定的 NFA 转换成一个等价的 DFA，方法是使用子集构造法。

子集构造法的核心思想是：DFA 的每一个状态对应 NFA 的一个状态子集。DFA 在某个状态下读入一个输入字符后，它会转移到一个新的状态，这个新状态对应的新子集，是原 NFA 从旧子集中的所有状态出发，经过该输入字符以及所有可能的 $\epsilon$-转移后，能够到达的所有状态的集合。

第一步：确定 NFA 的基本信息

• 状态集 Q: $\{q_0, q_1, q_2\}$
• 字母表 $\Sigma$: $\{a, b\}$
• 起始状态: $q_0$
• 接受状态 F: $\{q_2\}$
• 转移函数 $\delta$:
• $\delta(q_0, a) = \{q_1\}$
• $\delta(q_0, b) = \{q_0\}$
• $\delta(q_1, a) = \{q_2\}$
• $\delta(q_1, b) = \{q_0, q_2\}$
• $\delta(q_2, a) = \emptyset$
• $\delta(q_2, b) = \{q_1\}$

第二步：开始构造 DFA

1. DFA 的起始状态:
   • DFA 的起始状态是包含 NFA 起始状态的子集，并包括从它出发可以经过 $\epsilon$-转移到达的所有状态。
   • 在这个 NFA 中，没有 $\epsilon$-转移。
   • 所以，DFA 的起始状态就是 $\{q_0\}$。我们将其标记为 DFA 的一个新状态，例如 S0。
   • S0 = {q_0}。
2. 从 DFA 的起始状态 S0 出发进行转移:
   • 输入 'a':
   • 从 S0 = {q_0} 中的每个状态出发，看在 NFA 中输入 'a' 能到达哪些状态。
   • 从 $q_0$ 输入 'a'，到达 $\{q_1\}$。
   • 由于没有 $\epsilon$-转移，所以 DFA 从 S0 输入 'a' 后到达的新状态是 $\{q_1\}$。
   • 这是一个我们没见过的新子集，我们将其标记为 S1。S1 = {q_1}。
   • 所以，$\delta_{DFA}(S0, a) = S1$。
   • 输入 'b':
   • 从 S0 = {q_0} 中的 $q_0$ 出发，输入 'b'，到达 $\{q_0\}$。
   • 所以 DFA 从 S0 输入 'b' 后到达的新状态是 $\{q_0\}$，也就是 S0 本身。
   • 所以，$\delta_{DFA}(S0, b) = S0$。
3. 处理新发现的状态 S1:
   • 我们现在有了一个新状态 S1 = {q_1}，需要计算它的转移。
   • 输入 'a':
   • 从 $q_1$ 输入 'a'，到达 $\{q_2\}$。
   • 这是一个新子集，我们标记为 S2。S2 = {q_2}。
   • 所以，$\delta_{DFA}(S1, a) = S2$。
   • 输入 'b':
   • 从 $q_1$ 输入 'b'，到达 $\{q_0, q_2\}$。
   • 这是一个新子集，我们标记为 S3。S3 = {q_0, q_2}。
   • 所以，$\delta_{DFA}(S1, b) = S3$。
4. 处理新发现的状态 S2:
   • 我们现在有了新状态 S2 = {q_2}。
   • 输入 'a':
   • 从 $q_2$ 输入 'a'，到达 $\emptyset$（空集）。
   • 空集是一个新子集，我们标记为 S_dead (死亡状态)。S_dead = {}。
   • 所以，$\delta_{DFA}(S2, a) = S_{dead}$。
   • 输入 'b':
   • 从 $q_2$ 输入 'b'，到达 $\{q_1\}$。
   • 子集 $\{q_1\}$ 是我们已经见过的 S1。
   • 所以，$\delta_{DFA}(S2, b) = S1$。
5. 处理新发现的状态 S3:
   • 我们现在有了新状态 S3 = {q_0, q_2}。
   • 输入 'a':
   • 从 $q_0$ 输入 'a' 到达 $\{q_1\}$。
   • 从 $q_2$ 输入 'a' 到达 $\emptyset$。
   • 将结果并集起来：$\{q_1\} \cup \emptyset = \{q_1\}$。
   • 子集 $\{q_1\}$ 是我们已经见过的 S1。
   • 所以，$\delta_{DFA}(S3, a) = S1$。
   • 输入 'b':
   • 从 $q_0$ 输入 'b' 到达 $\{q_0\}$。
   • 从 $q_2$ 输入 'b' 到达 $\{q_1\}$。
   • 将结果并集起来：$\{q_0\} \cup \{q_1\} = \{q_0, q_1\}$。
   • 这是一个新子集，我们标记为 S4。S4 = {q_0, q_1}。
   • 所以，$\delta_{DFA}(S3, b) = S4$。
6. 处理新发现的死亡状态 S_dead:
   • S_dead = {}。
   • 输入 'a': 从空集中的状态出发，什么也到不了，结果还是空集 $\emptyset$。所以 $\delta_{DFA}(S_{dead}, a) = S_{dead}$。
   • 输入 'b': 同理，$\delta_{DFA}(S_{dead}, b) = S_{dead}$。
   • 这是一个陷阱状态，一旦进入就无法离开。
7. 处理新发现的状态 S4:
   • S4 = {q_0, q_1}。
   • 输入 'a':
   • 从 $q_0$ 输入 'a' 到达 $\{q_1\}$。
   • 从 $q_1$ 输入 'a' 到达 $\{q_2\}$。
   • 并集: $\{q_1\} \cup \{q_2\} = \{q_1, q_2\}$。
   • 这是一个新子集，我们标记为 S5。S5 = {q_1, q_2}。
   • 所以，$\delta_{DFA}(S4, a) = S5$。
   • 输入 'b':
   • 从 $q_0$ 输入 'b' 到达 $\{q_0\}$。
   • 从 $q_1$ 输入 'b' 到达 $\{q_0, q_2\}$。
   • 并集: $\{q_0\} \cup \{q_0, q_2\} = \{q_0, q_2\}$。
   • 子集 $\{q_0, q_2\}$ 是我们已经见过的 S3。
   • 所以，$\delta_{DFA}(S4, b) = S3$。
8. 处理新发现的状态 S5:
   • S5 = {q_1, q_2}。
   • 输入 'a':
   • 从 $q_1$ 输入 'a' 到达 $\{q_2\}$。
   • 从 $q_2$ 输入 'a' 到达 $\emptyset$。
   • 并集: $\{q_2\} \cup \emptyset = \{q_2\}$。
   • 子集 $\{q_2\}$ 是我们已经见过的 S2。
   • 所以，$\delta_{DFA}(S5, a) = S2$。
   • 输入 'b':
   • 从 $q_1$ 输入 'b' 到达 $\{q_0, q_2\}$。
   • 从 $q_2$ 输入 'b' 到达 $\{q_1\}$。
   • 并集: $\{q_0, q_2\} \cup \{q_1\} = \{q_0, q_1, q_2\}$。
   • 这是一个新子集，我们标记为 S6。S6 = {q_0, q_1, q_2}。
   • 所以，$\delta_{DFA}(S5, b) = S6$。
9. 处理新发现的状态 S6:
   • S6 = {q_0, q_1, q_2}。
   • 输入 'a':
   • 从 $q_0$ 到 $\{q_1\}$。从 $q_1$ 到 $\{q_2\}$。从 $q_2$ 到 $\emptyset$。
   • 并集: $\{q_1, q_2\}$，即 S5。
   • 所以，$\delta_{DFA}(S6, a) = S5$。
   • 输入 'b':
   • 从 $q_0$ 到 $\{q_0\}$。从 $q_1$ 到 $\{q_0, q_2\}$。从 $q_2$ 到 $\{q_1\}$。
   • 并集: $\{q_0, q_1, q_2\}$，即 S6 本身。
   • 所以，$\delta_{DFA}(S6, b) = S6$。
10. 确定 DFA 的接受状态:
    • DFA 的一个状态是接受状态，当且仅当它对应的 NFA 状态子集包含至少一个 NFA 的接受状态。
    • NFA 的接受状态是 $\{q_2\}$。
    • 检查我们所有的 DFA 状态：
    • S0 = {q_0}: 不含 $q_2$，非接受。
    • S1 = {q_1}: 不含 $q_2$，非接受。
    • S2 = {q_2}: 包含 $q_2$，是接受状态。
    • S3 = {q_0, q_2}: 包含 $q_2$，是接受状态。
    • S_dead = {}: 不含 $q_2$，非接受。
    • S4 = {q_0, q_1}: 不含 $q_2$，非接受。
    • S5 = {q_1, q_2}: 包含 $q_2$，是接受状态。
    • S6 = {q_0, q_1, q_2}: 包含 $q_2$，是接受状态。

第三步：绘制最终的 DFA

将上述所有转移关系和接受状态画成一个状态图，就得到了最终的 DFA。

这个问题展示了如何利用正规语言在并集运算下的封闭性来构造一个新的自动机。封闭性意味着，如果 $L_1$ 和 $L_2$ 都是正规语言，那么它们的并集 $L_1 \cup L_2$ 也必然是正规语言。我们可以通过构造一个识别 $L_1 \cup L_2$ 的 NFA 来证明这一点。

第一步：分析两个语言及其 DFA

• 语言 $L_1$: 包含偶数个 0 的所有二进制字符串。
• DFA for $L_1$:
• $q_0$: 起始状态，表示已看到偶数个 0 (包括 0 个)。这是接受状态。
• $q_1$: 表示已看到奇数个 0。这不是接受状态。
• 转移: 读到 '1' 不改变 0 的奇偶性，状态不变。读到 '0' 改变 0 的奇偶性，状态在 $q_0$ 和 $q_1$ 之间切换。

• 语言 $L_2$: 不包含连续两个 '1' ("11") 的所有二进制字符串。
• DFA for $L_2$:
• $p_0$: 起始状态，最近没有看到 '1'，或者刚看到 '0'。这是接受状态。
• $p_1$: 刚刚看到了一个 '1'。这也是接受状态。
• $p_2$: 已经看到了连续的 "11"。这是一个“陷阱”状态或“死亡”状态，非接受，并且任何输入都会留在这里。
• 转移:
• 在 $p_0$，读 '0' 留在 $p_0$，读 '1' 到 $p_1$。
• 在 $p_1$，读 '0' 回到 $p_0$，读 '1' 则触发了 "11"，进入陷阱状态 $p_2$。
• 在 $p_2$，任何输入都留在 $p_2$。

第二步：构造识别 $L_1 \cup L_2$ 的 NFA

构造并集的 NFA 的标准方法非常直观：

1. 创建一个全新的起始状态，我们称之为 $s$。
2. 从新起始状态 $s$ 出发，画两条 $\epsilon$-转移（空转移）。一条指向 $L_1$ 的 DFA 的起始状态 $q_0$，另一条指向 $L_2$ 的 DFA 的起始状态 $p_0$。
3. 保留原来两个 DFA 的所有状态和转移。
4. 保留原来两个 DFA 的所有接受状态。在这个例子中，$q_0, p_0, p_1$ 都是最终 NFA 的接受状态。

工作原理:

当这个新的 NFA 开始处理一个输入字符串时，它会从状态 $s$ 开始。由于有两条 $\epsilon$-转移，它会立刻、不消耗任何输入地“分裂”成两条并行的计算路径：

• 路径 1: 进入 $q_0$，然后完全按照 $L_1$ 的 DFA 规则进行计算。
• 路径 2: 进入 $p_0$，然后完全按照 $L_2$ 的 DFA 规则进行计算。

在字符串处理完毕后，只要这两条路径中至少有一条停在了接受状态，整个字符串就被这个新的 NFA 接受。这完美地对应了并集的定义：一个字符串属于 $L_1 \cup L_2$，当且仅当它属于 $L_1$ 或属于 $L_2$。

这个问题展示了如何利用正规语言在连接（concatenation）运算下的封闭性来构造一个新的自动机。如果 $L_1$ 和 $L_2$ 是正规语言，那么它们的连接 $L_1L_2 = \{xy \mid x \in L_1, y \in L_2\}$ 也是正规语言。

第一步：分析两个语言及其 NFA

• 语言 $L_1$: 包含奇数个 1 或 恰好有两个 0 的所有二进制字符串。
• 这是一个“或”类型的语言，所以它的 NFA (我们称之为 $N_1$) 本身就是通过并集构造得到的（类似于问题 4b）。
• 从图中可以看出，$N_1$ 有一个起始状态 $s_0$，它通过 $\epsilon$-转移连接到两个子模块：
• 上半部分：识别“奇数个 1”。有两个状态，一个代表偶数个 1（非接受），一个代表奇数个 1（接受）。
• 下半部分：识别“恰好有两个 0”。有三个状态，分别代表 0 个、1 个、2 个 0。最后一个状态是接受状态。
• $N_1$ 的接受状态是 $q_1$ 和 $c_2$。

• 语言 $L_2$: 以 "101" 结尾的所有二进制字符串。
• 它的 NFA (我们称之为 $N_2$) 的构造类似于问题 1a，但是是识别“以...结尾”，所以接受状态后面没有自循环。
• $p_0 \xrightarrow{0,1} p_0$：等待 "101" 的开始。
• $p_0 \xrightarrow{1} p_1$：匹配到 '1'。
• $p_1 \xrightarrow{0} p_2$：匹配到 '10'。
• $p_2 \xrightarrow{1} p_3$：匹配到 '101'。$p_3$ 是接受状态。

第二步：构造识别 $L_1L_2$ 的 NFA

构造连接 $N_1N_2$ 的 NFA 的标准方法是：

1. 将 $N_1$ 的所有接受状态连接到 $N_2$ 的起始状态。这个连接通过 $\epsilon$-转移实现。
2. $N_1$ 的起始状态 成为新 NFA 的起始状态。
3. $N_2$ 的接受状态 成为新 NFA 的接受状态。
4. $N_1$ 原来的接受状态不再是接受状态（因为它们现在是中间站，而不是终点）。

工作原理:

这个构造模拟了语言连接的定义 $xy$。

• 首先，自动机从 $N_1$ 的起始状态 $s_0$ 开始，处理输入字符串的前半部分。
• 如果这部分字符串能在 $N_1$ 中走到一个接受状态（比如 $q_1$ 或 $c_2$），这就意味着前半部分字符串 $x$ 属于 $L_1$。
• 此时，自动机不停止，而是通过一条 $\epsilon$-转移，“跳”到 $N_2$ 的起始状态 $p_0$。这个跳转不消耗任何输入字符。
• 然后，自动机从 $p_0$ 开始，继续处理输入字符串的后半部分。
• 如果后半部分字符串 $y$ 能让 $N_2$ 走到它的接受状态 $p_3$，那么就意味着 $y \in L_2$。
• 整个过程成功完成，字符串 $xy$ 被接受。

NFA 的非确定性在这里至关重要，因为它需要“猜测”在哪里分割字符串，即在哪里从 $N_1$ 跳转到 $N_2$。

这个问题通过一系列失败的尝试，来引导我们理解构造克莱尼星号 (Kleene Star) 的正确方法。克莱尼星号 $L^*$ 的定义是：由 $L$ 中的字符串任意连接 0 次或多次形成的所有字符串的集合。即 $L^* = L^0 \cup L^1 \cup L^2 \cup \dots$，其中 $L^0 = \{\epsilon\}$。

失败尝试 1：简单地将接受状态变起始状态，或加回指的边

这个尝试的核心错误在于没有正确处理空字符串 $\epsilon$。

• 语言 L: $\{10\}$。它的 DFA 很简单：$q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2$ (接受)。
• 语言 $L^*$: $\{\epsilon, 10, 1010, 101010, \dots\}$。
• 错误构造 1: 将原 DFA 的接受状态 $q_2$ 直接用一条边指回起始状态 $q_0$。
• 分析错误:

1. 空字符串 $\epsilon$: 语言 $L^*$ 必须包含 $\epsilon$。在这个错误的 NFA 中，起始状态 $q_0$ 不是接受状态。要接受 $\epsilon$，自动机必须在不消耗任何输入的情况下停在接受状态。显然，这个构造做不到。因此，这个构造至少漏掉了 $\epsilon$。
2. 接受 "10": $q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2$。$q_2$ 是接受状态，可以接受。
3. 接受 "1010": $q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{\text{错误构造的边?}} q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2$。这里假设从 $q_2$ 有一条 $\epsilon$ 边回到 $q_0$。这样可以接受 "1010"。
   • 核心缺陷: 最根本的问题是它不接受 $\epsilon$。任何对 $L$ 的星号运算 $L^*$，只要 $L$ 本身不是只包含 $\epsilon$ 的语言或者空语言，那么 $L^*$ 都会包含 $\epsilon$。而原语言 $L=\{10\}$ 不包含 $\epsilon$，所以它的 DFA 的起始状态不是接受状态。简单地加一条返回的边无法改变起始状态的性质。

正确的构造方法应该是什么样？

1. 处理 $\epsilon$: 为了接受 $\epsilon$，最直接的方法是让起始状态本身就是接受状态。
2. 处理重复: 为了接受 $L$ 中字符串的多次重复，需要从原自动机的接受状态返回到起始状态。

正确的构造（稍后会看到）是：

1. 创建一个新的起始状态 $s_{new}$，并让它成为接受状态（这就解决了 $\epsilon$ 的问题）。
2. 从 $s_{new}$ 画一条 $\epsilon$-转移到旧的起始状态 $q_0$。
3. 从旧的所有接受状态（这里是 $q_2$）画一条 $\epsilon$-转移回到旧的起始状态 $q_0$（实现循环）。

失败尝试 2：将起始状态直接设为接受状态

这个尝试吸取了上一个失败的教训，试图解决 $\epsilon$ 的问题。

• 语言 L: 所有以 "01" 结尾的字符串。
• $L$ 的 NFA: $q_0$ 有 (0,1) 自循环，然后 $q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2$ (接受)。
• 语言 $L^*$: $\{\epsilon\} \cup L$。这里有一个有趣的性质：由于 $L$ 是“以...结尾”的语言，任何两个 $L$ 中字符串的连接，结果仍然是以 "01" 结尾，所以 $L \cdot L \subseteq L$。因此，$L^*$ 就简化为了 $\{\epsilon\} \cup L$。
• 错误构造 2: 直接将原 NFA 的起始状态 $q_0$ 变成接受状态。
• 分析错误:

1. 它能接受正确的字符串吗？
   • 接受 $\epsilon$: 能。因为起始状态 $q_0$ 现在是接受状态。
   • 接受 $L$ 中的字符串 (如 "101"): 能。$q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2$。停在 $q_2$，是接受状态。
2. 它接受了不该接受的字符串吗？
   • 是的，这是问题的关键。
   • 考虑字符串 "0"。计算路径是 $q_0 \xrightarrow{0} q_0$。字符串结束，停在 $q_0$。由于这个构造把 $q_0$ 变成了接受状态，所以 "0" 被错误地接受了。
   • 但 "0" 并不在 $L^* = \{\epsilon\} \cup L$ 中，因为它既不是 $\epsilon$，也不以 "01" 结尾。
   • 同理，任何不以 "01" 结尾的非空字符串，比如 "11", "000", "1010"，都会停在 $q_0$ 或 $q_1$，但因为 $q_0$ 是接受的，所以只要能回到 $q_0$ 的前缀都会被接受。实际上，由于 $q_0$ 的自循环，任何字符串都能在 $q_0$ 结束一个计算分支，所以这个错误的 NFA 接受了所有字符串 $\Sigma^*$。

• 核心缺陷: 污染了起始状态。原 NFA 的起始状态 $q_0$ 具有“正在读取字符串，但尚未完成匹配”的语义。将其强行变为接受状态，就破坏了这种语义，导致所有尚未完成匹配的前缀都被错误地接受了。

失败尝试 3：增加一个新接受状态，并从起始状态 $\epsilon$-转移过去

这个尝试是上一个的变体，它试图通过增加一个全新的状态来避免“污染”起始状态。

• 语言 L 和 $L^*$: 同上。
• 错误构造 3:

1. 保留原 NFA 不变。
2. 创建一个新的状态 $q_{new}$，并将其设为接受状态。
3. 从原 NFA 的起始状态 $q_0$ 到这个新接受状态 $q_{new}$ 画一条 $\epsilon$-转移。
4. 让 $q_0$ 仍然是起始状态。

• 分析错误:
• 这个构造在逻辑上和失败尝试 2 是等价的。为什么呢？
• 在 NFA 中，如果一个状态 $A$ 可以通过 $\epsilon$-转移到达一个接受状态 $B$，那么状态 $A$ 本身在功能上也等同于一个接受状态。
• 因为任何计算路径只要到达了 $A$，它就可以不消耗任何输入，立刻“免费”跳转到 $B$，从而使得整个路径成为一条接受路径。
• 在这个构造中，$q_0$ 可以通过 $\epsilon$-转移到达新的接受状态 $q_{new}$。因此，任何停在 $q_0$ 的计算路径实际上都是成功的。
• 这和直接把 $q_0$ 设为接受状态（失败尝试 2）造成了完全相同的后果：所有能回到 $q_0$ 的前缀都被错误地接受了，导致整个 NFA 接受了所有字符串 $\Sigma^*$。

• 核心缺陷: 仍然是起始状态被“污染”了，只不过这次是间接污染。通过 $\epsilon$-转移，接受的性质从 $q_{new}$ “传递”给了 $q_0$。

失败尝试 4：从接受状态 $\epsilon$-转移到新接受状态，并让新状态成为循环点

这个尝试是之前所有失败尝试的某种混合，想法更加复杂，但也同样存在缺陷。

• 语言 L: $\{10\}$。
• 语言 $L^*$: $\{\epsilon, 10, 1010, \dots\}$。
• 错误构造 4:

1. 保留原 NFA ($q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2$)。
2. 创建一个新的状态 $q_{new}$，并设为接受状态。
3. 从原 NFA 的接受状态 $q_2$ 到 $q_{new}$ 画一条 $\epsilon$-转移。
4. 让 $q_{new}$ 成为新的起始状态。
5. 从 $q_{new}$ 到原 NFA 的起始状态 $q_0$ 画一条 $\epsilon$-转移。

• 分析错误:

1. 它能接受 $\epsilon$ 吗？
   • 能。因为新的起始状态 $q_{new}$ 本身就是接受状态。
2. 它能接受 "10" 吗？
   • 能。路径是 $q_{new} \xrightarrow{\epsilon} q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2$。停在 $q_2$ (非接受)，但可以继续 $\epsilon$-转移到 $q_{new}$ (接受)。所以接受。
3. 它能接受 "1010" 吗？
   • 不能。这是问题的关键。
   • 让我们追踪路径：$q_{new} \xrightarrow{\epsilon} q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{\epsilon} q_{new}$。到这里，字符串 "10" 被消耗完毕，自动机回到了起始状态 $q_{new}$。
   • 现在要处理后半部分的 "10"。自动机会再次沿着路径 $q_{new} \xrightarrow{\epsilon} q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2$。
   • 但是，当它从 $q_2$ 再次尝试进行 $\epsilon$-转移时，它只能到达 $q_{new}$。它无法回到 $q_0$ 去开始下一次循环。
   • 这个构造中，循环的路径是 $q_0 \to q_1 \to q_2 \to q_{new} \to q_0$。但是，字符串的消耗只发生在 $q_0 \to q_1 \to q_2$ 这一段。一旦到了 $q_{new}$，再想开始新一轮的 "10" 匹配，就必须再次回到 $q_0$。而这个构造中，从 $q_2$ 无法直接回到 $q_0$。

• 核心缺陷: 循环路径设置错误。正确的循环应该是完成一次匹配后，能回到开始下一次匹配的地方。这个构造让它回到了一个“终点兼起点”($q_{new}$)，但从这个点出发，虽然能到达 $q_0$，但完成匹配后($q_2$)却无法再次回到 $q_0$。它把“完成一次”和“准备下一次”的路径搞混了。

这个问题要求证明正规语言对于逆转 (reversal) 运算是封闭的。一个语言 $L$ 的逆转 $L^R$ 是将 $L$ 中每个字符串都反写过来得到的语言。例如，如果 $L = \{ab, cde\}$，那么 $L^R = \{ba, edc\}$。

证明思路是构造性的：如果我们有一个识别 $L$ 的自动机 $A$，我们能否通过改造它来得到一个识别 $L^R$ 的自动机 $B$？

直观想法: 如果字符串 $w$ 能让自动机 $A$ 从起始状态走到接受状态，那么它的逆转字符串 $w^R$ 应该能让新自动机 $B$ 从原来的接受状态“倒着走”回到原来的起始状态。

这启发我们进行以下改造：

1. 反转所有转移箭头: 如果在 $A$ 中有 $q_i \xrightarrow{a} q_j$，那么在 $B$ 中就应该有 $q_j \xrightarrow{a} q_i$。
2. 交换起始和接受状态:
   • $A$ 的起始状态应该成为 $B$ 的接受状态。
   • $A$ 的接受状态应该成为 $B$ 的起始状态。

出现的问题:

• 一个 DFA (或 NFA) 只能有一个起始状态，但它可能有很多个接受状态。当我们把 $A$ 的所有接受状态都变成 $B$ 的“起始状态”时，就违反了这个规则。
• 一个状态对于一个输入，在 DFA 中只有一个出边。反转后，一个状态对于一个输入，可能有很多个出边（因为在原 DFA 中，可能有很多状态通过同一个字符转移到这个状态）。因此，反转后的自动机通常是一个 NFA，而不是 DFA。

标准构造方法 (生成 NFA):

为了解决上述问题，我们构造一个 NFA $B$ 来识别 $L^R$，步骤如下：

1. 状态: 保留 $A$ 的所有状态，并增加一个全新的起始状态 $q_0'$。
2. 起始状态: 新的 NFA $B$ 的起始状态就是这个 $q_0'$。
3. 转移:
   • 反转箭头: 对于 $A$ 中的每一个转移 $\delta_A(q, a) = r$，我们在 $B$ 中添加一个转移 $\delta_B(r, a)$ 包含 $q$。
   • 处理多“起始”点: 从新的起始状态 $q_0'$ 画 $\epsilon$-转移到 $A$ 中所有的接受状态 $F_A$。这相当于说：“你可以从任何一个原来的终点开始你的‘逆向旅程’。”
4. 接受状态: 将 $A$ 的原起始状态 $q_0$ 设为 $B$ 的唯一接受状态。

图示例子:

• $L$ 的 DFA: 识别以 'b' 结尾的语言 $L = (a \cup b)^*b$。
• $q_0$ (起始), $q_1$ (接受)。
• $q_0 \xrightarrow{a} q_0$, $q_0 \xrightarrow{b} q_1$。
• $q_1 \xrightarrow{a} q_0$, $q_1 \xrightarrow{b} q_1$。
• 构造 $L^R$ 的 NFA: $L^R$ 是以 'b' 开头的语言。

1. 新起始状态: $q_0'$。
2. 新接受状态: $\{q_0\}$。
3. 反转箭头:
   • $q_0 \xleftarrow{a} q_0$, $q_1 \xleftarrow{b} q_0$
   • $q_0 \xleftarrow{a} q_1$, $q_1 \xleftarrow{b} q_1$
4. 添加 $\epsilon$-转移: 从 $q_0'$ 到原接受状态 $q_1$ 添加 $\epsilon$-转移。
   • 这样得到的 NFA (图示右侧)，它的起始状态是 $q_0'$，接受状态是 $q_0$。让我们看看它是否识别以 'b' 开头的语言。
   • 对于 "ba"：$q_0' \xrightarrow{\epsilon} q_1 \xrightarrow{b} q_1 \xrightarrow{a} q_0$。停在接受状态 $q_0$，接受。正确。
   • 对于 "b"：$q_0' \xrightarrow{\epsilon} q_1 \xrightarrow{b} q_1$。停在非接受状态 $q_1$，拒绝。等等，"b" 应该被接受！
   • 啊哈，图示中有一个微妙之处：仔细看右图，从 $q_0'$ 出发有两条 $\epsilon$-转移，一条到 $q_0$，一条到 $q_1$。这是因为原图的 $q_0$ 状态没有被明确标为非接受，如果 $L$ 包含 $\epsilon$，那么 $q_0$ 也是接受状态。但在这个例子里，$L$ 不含 $\epsilon$。我们假设只有 $q_1$ 是接受。那么，从 $q_0'$ 只需 $\epsilon$-转移到 $q_1$。
   • 再次检查 "b": $q_0' \xrightarrow{\epsilon} q_1 \xrightarrow{b} q_1$。停在 $q_1$，非接受。为什么？因为原语言是 (a|b)b，而逆转 b(a|b) 包含 "b"。
   • 让我们重新审视原图：原图 $L$ 的 DFA 描述的是“以b结尾”。$q_0$ 读a留在 $q_0$，读b到 $q_1$。$q_1$ 读a到 $q_0$，读b留在 $q_1$。$q_0$ 是起始， $q_1$ 是接受。这是正确的。
   • 那么 $L^R$ 的 NFA 为什么拒绝了 "b"？让我们重新走一遍构造。
   • $A$ 的接受状态是 $F_A = \{q_1\}$。
   • $B$ 的起始状态 $q_0'$，接受状态 $F_B = \{q_0\}$。
   • $\delta_B(q_0', \epsilon) = \{q_1\}$。
   • $\delta_A(q_0, a)=q_0 \implies q_0 \in \delta_B(q_0, a)$。
   • $\delta_A(q_1, a)=q_0 \implies q_1 \in \delta_B(q_0, a)$。所以 $\delta_B(q_0, a) = \{q_0, q_1\}$。(图中画的箭头是从 $q_0$ 到 $q_1$)
   • $\delta_A(q_0, b)=q_1 \implies q_0 \in \delta_B(q_1, b)$。
   • $\delta_A(q_1, b)=q_1 \implies q_1 \in \delta_B(q_1, b)$。所以 $\delta_B(q_1, b) = \{q_0, q_1\}$。(图中画的箭头是从 $q_1$ 到 $q_0$ 和 $q_1$)
   • 图示画错了！ 解答中的图示与它自己描述的构造规则不完全一致。这是一个常见的讲义错误。根据构造规则，从 $q_0$ 输入 a 应该能到 $q_0$ 和 $q_1$。但图中只画了到 $q_1$。
   • 让我们忽略图中的小错误，用正确的逻辑来验证: 识别 $L^R = b(a|b)^*$ 的 NFA 应该是什么样的？一个简单的 NFA 是 $s_0 \xrightarrow{b} s_1$，其中 $s_1$ 是接受状态且有 (a,b) 自循环。我们的构造是否等价于这个？
   • $q_0' \xrightarrow{\epsilon} q_1$。
   • $q_1 \xrightarrow{b} \{q_0, q_1\}$。
   • $q_0$ 是接受状态。所以读入 "b" 之后，一条路径到 $q_0$，一条到 $q_1$。因为到达了接受状态 $q_0$，所以 "b" 被接受。
   • 这说明构造本身是正确的，但图示可能为了简化而省略了一些细节，或者有误。

这部分是上一个构造的严格数学证明，旨在展示如何形式化地论证一个构造的正确性。证明一个自动机 $B$ 识别一个语言 $L_B$ 的标准方法是证明一个双向蕴含关系：一个字符串 $w$ 属于语言 $L_B$ 当且仅当自动机 $B$ 接受字符串 $w$。

证明目标: $w^R \in L^R \iff B \text{ 接受 } w^R$。

第一部分：正向证明 ($\Longrightarrow$)

• 前提: 假设 $w^R \in L^R$。
• 目标: 证明 NFA $B$ 接受 $w^R$。
• 推导链:

1. 如果 $w^R \in L^R$，根据逆转定义，那么原字符串 $w \in L$。
2. 因为 DFA $A$ 识别 $L$，所以存在一条在 $A$ 中接受 $w$ 的计算路径。设 $w = a_1a_2...a_n$。这条路径可以写成状态序列：$s_0, s_1, ..., s_n$，其中 $s_0=q_0$ (A的起始)，$s_n \in F_A$ (A的接受状态集)，并且对于每一步 $i$ (从 0 到 n-1)，都有 $\delta_A(s_i, a_{i+1}) = s_{i+1}$。
3. 现在我们要在 NFA $B$ 中为 $w^R = a_n...a_2a_1$ 构造一条接受路径。
4. $B$ 的计算从其起始状态 $q_0'$ 开始。
5. 根据构造，从 $q_0'$ 有一条 $\epsilon$-转移到所有 $A$ 的接受状态。因为 $s_n \in F_A$，所以 $B$ 可以从 $q_0'$ 经过 $\epsilon$-转移到达状态 $s_n$。
6. 接下来，$B$ 需要消耗 $w^R$ 的第一个字符 $a_n$。在 $A$ 中，我们有 $\delta_A(s_{n-1}, a_n) = s_n$。根据 $B$ 的构造（箭头反转），在 $B$ 中必然存在一个转移，使得从状态 $s_n$ 读入 $a_n$ 可以到达状态 $s_{n-1}$。
7. 依此类推，对于 $w^R$ 的每一个字符 $a_i$ (从 $n$ 到 1)，在 $B$ 中都存在一条路径 $s_i \xrightarrow{a_i} s_{i-1}$。
8. 这样，我们就在 $B$ 中构建了一条完整的计算路径：$q_0' \xrightarrow{\epsilon} s_n \xrightarrow{a_n} s_{n-1} \xrightarrow{a_{n-1}} \dots \xrightarrow{a_2} s_1 \xrightarrow{a_1} s_0$。
9. 这条路径的终点是 $s_0$。根据构造，$s_0$ (即 $A$ 的原起始状态) 正是 $B$ 的接受状态。
10. 结论: 我们成功地为 $w^R$ 在 $B$ 中找到了一条接受路径。因此，$B$ 接受 $w^R$。

第二部分：反向证明 ($\Longleftarrow$)

• 前提: 假设 NFA $B$ 接受 $w^R$。
• 目标: 证明 $w^R \in L^R$。
• 推导链:

1. 如果 $B$ 接受 $w^R = a_n...a_1$，那么在 $B$ 中一定存在一条从起始状态 $q_0'$ 到接受状态 $q_0$ (即 $F_B$) 的路径。
2. 这条路径必然以 $q_0' \xrightarrow{\epsilon} s_n$ 开始，其中 $s_n$ 是 $A$ 的一个接受状态 ($s_n \in F_A$)。
3. 然后，路径必须是 $s_n \xrightarrow{a_n} s_{n-1} \dots \xrightarrow{a_1} s_0$，其中终点 $s_0$ 必须是 $B$ 的接受状态，也就是 $A$ 的原起始状态。
4. 由于 $B$ 的转移是 $A$ 的转移的逆向，那么对于 $B$ 中的每一步 $s_i \xrightarrow{a_i} s_{i-1}$，在 $A$ 中都必然存在一步 $\delta_A(s_{i-1}, a_i) = s_i$。
5. 将 $B$ 的整个计算路径反过来看，我们在 $A$ 中就得到了一条路径：$s_0 \xrightarrow{a_1} s_1 \xrightarrow{a_2} \dots \xrightarrow{a_n} s_n$。
6. 这条路径在 $A$ 中，从起始状态 $s_0$ 开始，到接受状态 $s_n$ 结束，消耗的字符串是 $w = a_1a_2...a_n$。
7. 因此，$A$ 接受字符串 $w$，即 $w \in L$。
8. 根据逆转的定义，如果 $w \in L$，那么 $w^R \in L^R$。
9. 结论: 我们证明了如果 $B$ 接受 $w^R$，那么 $w^R$ 必然属于语言 $L^R$。

最终结论:

由于双向蕴含关系都已证明，所以我们得出结论：NFA $B$ 识别的语言恰好是 $L^R$。因为我们能够为任何正规语言 $L$ 构造出这样一个识别 $L^R$ 的 NFA，所以 $L^R$ 也必然是正规语言。正规语言集合在逆转运算下是封闭的。

这个问题要求证明正规语言对一个名为 $\min$ 的运算是封闭的。首先我们需要理解 $\min(L)$ 的定义。

$\min(L)$ 的定义:

$\min(L) = \{w \in L \mid w \text{ 的任何真前缀都不在 } L \text{ 中}\}$。

一个字符串的真前缀是指该字符串的、不等于其自身的前缀。例如，"apple" 的真前缀有 $\epsilon$, "a", "ap", "app", "appl"。

$\min(L)$ 语言的本质是：保留 $L$ 中那些“最短”的、不可再缩短的被接受的字符串。如果一个字符串 $w$ 在 $L$ 中，但它的某个前缀 $x$ 也在 $L$ 中，那么 $w$ 就像是一个“多余”的、更长的版本，它会被 $\min(L)$ 丢弃。

构造思路:

我们要从一个识别 $L$ 的 DFA $A$ 出发，构造一个识别 $\min(L)$ 的 DFA $B$。

• 根据 $\min(L)$ 的定义，如果一个字符串 $w=xy$ 被 $A$ 接受，并且它的前缀 $x$ 也被 $A$ 接受，那么 $w$ 不应该被 $B$ 接受。
• 在 DFA $A$ 中，这意味着什么？如果处理前缀 $x$ 后，DFA $A$ 到达了一个接受状态，那么之后再处理后续的字符串 $y$ 时，无论最终停在哪里，整个字符串 $w=xy$ 都不属于 $\min(L)$。
• 这启发我们：一旦进入一个接受状态，就不能再“出来”继续进行有效的计算了。任何从接受状态出发的转移，都应该导向一个万劫不复的“失败”境地。

DFA $B$ 的构造步骤:

1. 状态: 复制 $A$ 的所有状态，并增加一个全新的拒绝状态（或称“陷阱状态”、“死亡状态”），记为 $q_{reject}$。
2. 起始状态: $B$ 的起始状态和 $A$ 的起始状态相同。
3. 接受状态: $B$ 的接受状态集合和 $A$ 的接受状态集合相同。
4. 修改转移:
   • 核心修改: 对于 $A$ 中所有的接受状态 $q$，在 $B$ 中，从 $q$ 出发的所有转移（无论输入什么字符）全部指向我们新加的 $q_{reject}$。
   • 陷阱状态的自循环: $q_{reject}$ 对所有输入都有一个指向自身的转移。一旦进入，永不离开。
   • 其他转移不变: 对于 $A$ 中所有非接受状态 $q$，它们原来的转移在 $B$ 中保持不变。

工作原理:

• 当 DFA $B$ 处理一个字符串 $w$ 时，只要它还没有遇到一个属于 $L$ 的前缀，它的行为就和 DFA $A$ 完全一样。
• 如果 $w$ 本身属于 $L$，并且没有任何真前缀属于 $L$，那么 $B$ 会和 $A$ 一样，在消耗完 $w$ 的最后一个字符时，恰好到达一个接受状态。因此，$w$ 被 $B$ 接受。
• 如果 $w$ 有一个真前缀 $x$ 属于 $L$ (设 $w=xy, y$ 非空)，那么当 $B$ 处理完前缀 $x$ 时，它会到达一个接受状态。但此时字符串还没结束，还需要处理 $y$。根据我们的新规则，从这个接受状态出发的第一步（即处理 $y$ 的第一个字符），就会立即让 $B$ 转移到 $q_{reject}$ 状态。之后无论 $y$ 剩下什么，B 都会一直停在 $q_{reject}$。最终字符串 $w$ 结束时，B 停在非接受的 $q_{reject}$ 状态，$w$ 被拒绝。

这个构造完美地实现了 $\min(L)$ 的定义。

这部分是对 min(L) 构造的正确性进行形式化证明。证明分为两个部分，对应于 min(L) 定义的两个方面。

第一部分：证明 $w \in \min (L) \Longrightarrow B \text{ 接受 } w$

• 前提: 假设 $w \in \min(L)$。
• 目标: 证明 DFA $B$ 接受 $w$。
• 推导链:

1. 根据 $\min(L)$ 的定义，如果 $w \in \min(L)$，那么它必须满足两个条件：
   • (a) $w \in L$。
   • (b) $w$ 的任何真前缀 $x$ 都不在 $L$ 中。
2. 从条件 (a) $w \in L$ 可知，DFA $A$ 在处理完 $w$ 后，会停在一个接受状态 $q_{final} \in F_A$。
3. 从条件 (b) 可知，对于 $w$ 的任何真前缀 $x$，DFA $A$ 在处理完 $x$ 后，会停在一个非接受状态。
4. 现在来看 DFA $B$ 的行为。当 $B$ 处理 $w$ 时，对于 $w$ 的所有真前缀 $x$，计算路径所经过的状态都是非接受状态。根据我们的构造，在这些非接受状态上，$B$ 的转移行为与 $A$ 完全相同。
5. 因此，在消耗完 $w$ 的最后一个字符之前，$B$ 的计算路径与 $A$ 的完全一样。
6. 当最后一个字符被消耗时，$B$ 会和 $A$ 一样，到达状态 $q_{final}$。
7. 因为 $F_B = F_A$，所以 $q_{final}$ 也是 $B$ 的一个接受状态。
8. 字符串处理结束，B 停在接受状态 $q_{final}$。
9. 结论: DFA $B$ 接受 $w$。

第二部分：证明 $w \notin \min (L) \Longrightarrow B \text{ 拒绝 } w$

• 前提: 假设 $w \notin \min(L)$。
• 目标: 证明 DFA $B$ 拒绝 $w$。
• 推导链:
• $w \notin \min(L)$ 意味着以下两种情况之一为真：
• 情况 1: $w$ 本身就不在 $L$ 中。

1. 如果 $w \notin L$，那么 DFA $A$ 处理完 $w$ 后会停在一个非接受状态。
2. 我们来分析 $B$ 的行为。在处理 $w$ 的过程中，如果路径从未经过任何 $A$ 的接受状态，那么 $B$ 的行为和 $A$ 完全一样，最终也会停在同一个非接受状态，因此拒绝 $w$。
3. 如果在处理 $w$ 的过程中，路径经过了某个 $A$ 的接受状态（即 $w$ 的某个前缀 $x \in L$），那么这就变成了下面的情况 2。
4. 因此，只要我们能证明情况 2 会导致拒绝，情况 1 也就被覆盖了。
   • 情况 2: $w \in L$ 但它有一个真前缀 $x$ 也在 $L$ 中。
5. 设 $w = xy$，其中 $x$ 是 $w$ 的一个真前缀（所以 $y$ 非空），并且 $x \in L$。
6. 当 DFA $B$ 开始处理 $w$ 时，它首先处理前缀 $x$。
7. 因为 $x \in L$，DFA $A$ 在处理完 $x$ 后会到达一个接受状态 $q_x \in F_A$。
8. 由于在到达 $q_x$ 之前，$B$ 的行为和 $A$ 一样，所以 $B$ 在处理完 $x$ 后也会到达 $q_x$。
9. 此时，字符串还没结束，B 需要继续处理 $y$ 的第一个字符，设为 $a$。
10. 根据我们的构造，从接受状态 $q_x$ 出发，对于任何输入 $a$，B 的下一状态是 $\delta_B(q_x, a) = q_{reject}$。
11. 一旦进入 $q_{reject}$ 状态，对于 $y$ 剩下的所有字符，B 都会一直停留在 $q_{reject}$。
12. 字符串 $w$ 处理完毕后，B 最终停在状态 $q_{reject}$。
13. $q_{reject}$ 不是接受状态。
14. 结论: DFA $B$ 拒绝 $w$。

最终结论:

两个方向的证明都已完成。我们证明了我们构造的 DFA $B$ 精确地识别了语言 $\min(L)$。因此，$\min(L)$ 是正规语言。

• 正则表达式: $0^*1^*$
• 拆解:
• $0^*$: 这里的 * 是克莱尼星号，表示它前面的元素 0 可以出现 0 次或任意多次。所以 $0^*$ 代表的语言是 $\{\epsilon, 0, 00, 000, \dots\}$。
• $1^*$: 同理，这代表 1 出现 0 次或任意多次。语言是 $\{\epsilon, 1, 11, 111, \dots\}$。
• 连接: 整个表达式是 $0^*$ 连接 $1^*$。连接操作意味着先从 $0^*$ 代表的语言里取一个字符串，然后从 $1^*$ 代表的语言里取一个字符串，把它们拼在一起。
• 语言描述:
• 取 $w_0 \in 0^*$ 和 $w_1 \in 1^*$，则语言中的字符串形式为 $w_0w_1$。
• 这意味着，字符串必须先由若干个（包括零个）'0' 组成，然后由若干个（包括零个）'1' 组成。
• 一旦出现了一个 '1'，后面就不能再出现 '0'。
• 形式化描述: $\{0^n 1^m \mid n \ge 0, m \ge 0\}$。$n$ 和 $m$ 分别代表 0 和 1 出现的次数，它们可以独立地取任何非负整数。

• 正则表达式: $(01)^*$
• 拆解:
• (01): 括号用于组合。01 表示字符 '0' 后面紧跟着字符 '1'。这是一个单元。
• $^*$: 克莱尼星号作用于括号里的整个单元 01。
• 语言描述:
• 这意味着 01 这个单元可以重复 0 次或任意多次。
• 形式化描述: $\{(01)^n \mid n \ge 0\}$。

• 正则表达式: $(0^*1^*)^*$
• 拆解:
• $0^*1^*$: 我们已经知道，这代表“任意个 0 后面跟任意个 1”。例如 $\epsilon, 0, 1, 00, 11, 01, 001$ 都在这个语言里。
• $()^*$: 最外层的星号表示，我们可以从括号里的语言 ($0^*1^*$) 中任意挑选字符串，然后把它们连接起来任意多次。
• 语言描述:
• 让我们看看能生成什么。
• 只选一次，可选 "01"。
• 只选一次，可选 "1"。
• 只选一次，可选 "0"。
• 选两次：第一次选 "1"，第二次选 "0"。拼起来就是 "10"。
• 既然我们可以生成 "0" 和 "1"，并且可以任意次地将它们连接起来，那么我们就能生成由 "0" 和 "1" 构成的任何字符串。例如，要生成 "101"，我们可以选三次：第一次选 "1"，第二次选 "0"，第三次选 "1"。
• 结论: 这个正则表达式可以生成字母表 $\{0, 1\}$ 上的所有可能字符串。
• 形式化描述: $\{0,1\}^*$。

• 正则表达式: $(0 \cup 1)^*$
• 拆解:
• $0 \cup 1$: $\cup$ 符号代表并集或“或”。所以 0 $\cup$ 1 代表的语言是 {0, 1}，即可以选 '0' 或者选 '1'。
• $()^*$: 星号作用于括号内的语言 {0, 1}。
• 语言描述:
• 这意味着我们可以从集合 {0, 1} 中任意挑选字符（'0' 或 '1'），并重复这个过程任意多次（0 次或多次）。
• 这正是“所有由 '0' 和 '1' 构成的字符串”的定义。
• 形式化描述: $\{0,1\}^*$。

为什么 $(0^*1^*)^*$ 和 $(0 \cup 1)^*$ 等价？

• $(0 \cup 1)^*$ 很明显是所有二进制字符串。我们需要证明 $(0^*1^*)^*$ 也能生成所有二进制字符串。
• 证明的关键在于证明 $(0^*1^*)^*$ 可以生成任意单个的 '0' 和任意单个的 '1'。
• 要生成 '0'，我们可以在 $(0^*1^*)^*$ 中只重复一次，那次选择 $0^*1^*$ 中的 "0" (令 n=1, m=0)。
• 要生成 '1'，我们可以在 $(0^*1^*)^*$ 中只重复一次，那次选择 $0^*1^*$ 中的 "1" (令 n=0, m=1)。
• 既然我们可以生成基本的构建块 '0' 和 '1'，并且外层的星号允许我们将这些构建块任意次地连接起来，那么我们自然可以构建出任何由 '0' 和 '1' 组成的字符串。
• 因此，$(0^*1^*)^*$ 描述的语言和 $(0 \cup 1)^*$ 描述的语言是相同的。

• 正则表达式: $0^*(10^*1)^*0^*$
• 拆解:
• $0^*$ (开头): 字符串可以由任意多个（包括 0 个）'0' 开始。
• $0^*$ (结尾): 字符串可以由任意多个（包括 0 个）'0' 结束。
• (10\*1): 这是核心部分。它描述了什么？
• 一个 '1'。
• 后面跟着任意多个 '0' ($0^*$)。
• 再后面跟着一个 '1'。
• 所以，10*1 描述的是一对 '1'，它们之间可以被任意多个 '0' 分隔。例如："11", "101", "1001"。
• $(10^*1)^*$: 星号作用于 10*1 这个单元。这意味着，这种“成对出现的 '1'”的模式可以重复 0 次或任意多次。
• 重复 0 次：语言是 $\epsilon$。
• 重复 1 次：语言是 $10^*1$。
• 重复 2 次：语言是 $(10^*1)(10^*1)$，例如 "11101"。
• 语言描述:
• 把所有部分组合起来看：$0^* (10^*1)^* 0^*$。
• 字符串的结构是：一堆 '0' (可选) + 一堆“成对的 '1' 模式” (可选) + 一堆 '0' (可选)。
• 关键在于 '1' 的数量。'1' 只出现在 (10*1) 这个部分。而这个部分每次都提供两个 '1'。由于这个部分可以重复任意次 ($n \ge 0$)，所以 '1' 的总数必然是 $2n$，即偶数。
• '0' 可以出现在开头、结尾，以及成对的 '1' 之间，所以 '0' 的数量和位置是任意的。
• 结论: 这个正则表达式描述的是所有包含偶数个 '1' 的二进制字符串。

• 语言: 所有以 "10" 开头的字符串。
• 分析:
• 一个字符串要满足这个条件，必须分为两部分：

1. 开头部分: 必须是固定的 "10"。
2. 结尾部分: 在 "10" 之后，可以是任何东西。
   • "任何东西" 在二进制字母表上，就是“任意由 0 和 1 组成的字符串”，其正则表达式是 $(0 \cup 1)^*$。
   • 构造:
   • 将这两部分连接起来即可。
   • 正则表达式: $10 (0 \cup 1)^*$。

• 语言: 恰好包含两个 '0' 的字符串。
• 分析:
• 整个字符串中必须有两个 '0'，不多也不少。
• '1' 可以出现任意多次，并且可以出现在任何位置：在第一个 '0' 之前，在两个 '0' 之间，以及在第二个 '0' 之后。
• 构造:
• 我们可以把结构想象成：(一些1) 0 (一些1) 0 (一些1)。
• "一些1" 或 "任意多个1" 的正则表达式是 $1^*$。
• 将这个模式替换到结构中：$1^* 0 1^* 0 1^*$。
• 验证:
• $1^*$ (开头): 允许在第一个 '0' 之前有任意多个 '1'。
• 0: 这是第一个必须出现的 '0'。
• $1^*$ (中间): 允许在两个 '0' 之间有任意多个 '1'。
• 0: 这是第二个必须出现的 '0'。
• $1^*$ (结尾): 允许在第二个 '0' 之后有任意多个 '1'。
• 这个结构保证了 '0' 恰好出现两次，而 '1' 可以自由地填充在这些 '0' 的周围。

• 语言: 包含奇数个 '0' 的字符串。
• 分析:
• 奇数个 '0' 意味着至少有一个 '0'，然后可以有任意多“成对的 '0'”。即 1 个，3 个，5 个...
• 我们可以把问题分解：一个'0' + 偶数个'0'。
• '1' 可以在任何地方出现。
• 构造:

1. 偶数个 '0' 的模块:
   • 我们如何表达“偶数个 '0'，中间可以任意插入 '1'”？
   • 一个想法是，'0' 总是成对出现的。从 (b) 小题，我们知道 $1^*01^*01^*$ 代表恰好两个 '0'，周围是任意 '1'。
   • 我们可以把这个 (1^01^01^*) 作为一个“产生一对 '0'”的单元。
   • 对其应用克莱尼星号 (1^01^01^)^，就代表了这个单元可以重复 0 次，1 次，2 次... 每次重复都增加两个 '0'。所以这部分就代表了“偶数个'0'，并且'1'可以任意分布”。
2. 奇数个 '0':
   • 我们只需要在上述“偶数个'0'”的模式基础上，再增加一个 '0' 即可。
   • 这个额外的 '0' 可以放在哪里？它可以放在最前面。
   • 我们需要一个 '0'，它前面可以有任意个 '1'。这部分是 $1^*0$。
   • 将这两部分连接起来：$1^*0$ (产生第一个'0') 连接 $(1^*01^*01^*)^*$ (产生后续成对的'0')。
   • 最终表达式: $1^*0(1^*01^*01^*)^*$
   • 解答练习: 将奇数 '0' 添加到前面还是后面有关系吗？
   • 表达式是 $1^*0 \text{ (偶数模块) } 1^*$ (因为最后的 '0' 后面也可能有 '1')。
   • 如果我们把单个 '0' 放到后面，比如 (偶数模块) 10 1，是否等价？
   • 偶数模块 是 (1^01^01^)^。
   • 前面：$1^*0(1^*01^*01^*)^*$。让我们考虑它能否生成 "01010"。
   • $1^*0$ 匹配第一个 "0"。
   • $(1^*01^*01^*)$ 匹配 "1010"。其中，第一个 $1^*$ 匹配 "1"，第一个 $0$ 匹配 "0"，第二个 $1^*$ 匹配 "1"，第二个 $0$ 匹配 "0"，第三个 $1^*$ 匹配 $\epsilon$。
   • 所以可以生成。
   • 后面：$(1^*01^*01^*)^* 1^*01^*$。让我们考虑能否生成 "01010"。
   • $(1^*01^*01^*)$ 匹配 "010"。这是不可能的，因为它需要两个 '0'。
   • 也许 $(1^*01^*01^*)$ 匹配 "01"？不可能。
   • 也许 $(1^*01^*01^*)$ 重复 0 次，即 $\epsilon$。那么表达式剩下 $1^*01^*$。这只能匹配含有一个 '0' 的字符串。
   • 这说明简单的把 $1^*0$ 放在后面是不行的。
   • 正确的思考方式: 整个字符串由任意多个 '1' 和奇数个 '0' 组成。
   • $1^*0(1^*01^*01^*)^*$ 的结构是 (任意1) (第一个0) (任意1和偶数个0)。
   • 等价的结构也可以是 (任意1和偶数个0) (最后一个0) (任意1)。
   • 所以 (1^01^01^)^ 1^0 1^ 也是可以的。
   • 答案给出的 10(10101) 是不完整的，因为它没有考虑最后一个'0'后面可能还有'1'。一个更完整的答案应该是 $1^*0(1^*01^*01^*)^*1^*$，或者 $1^*(1^*01^*01^*)^*01^*$。不过通常为了简化，末尾的 $1^*$ 如果可以被并入前面的星号表达式，可能会被省略。在 (10101)* 中，最后一个 $1^*$ 已经包含了处理结尾的 $1$ 的能力。所以答案 $1^{*} 0\left(1^{*} 01^{*} 01^{*}\right)^{*}$ 是正确的。

• 语言: 不包含子串 "abc" 的所有由 {a, b, c} 组成的字符串。
• 分析 (这是一个难题，通常用补集思想更容易):
• 直接构造“不包含”的正则表达式通常非常困难。
• 一个更系统的方法是：

1. 构造识别“包含”子串 "abc" 的语言的正则表达式。这个很简单：$(a \cup b \cup c)^* abc (a \cup b \cup c)^*$。
2. 将这个正则表达式转换为 NFA，再转换为 DFA。
3. 将这个 DFA 的接受状态和非接受状态对调，得到一个识别补集语言（即“不包含 a-b-c”）的 DFA。
4. 再将这个新的 DFA 转换回正则表达式。
   • 这个过程非常繁琐。解答中提供的是一种直接构造的思路，虽然巧妙但非常难以想到。

• 解答中的直接构造思路分析:
• 核心思想: 不要生成 "abc"。这意味着，每当出现一个 'a' 时，如果后面要跟 'b'，那么再后面就不能跟 'c'。
• 或者反过来看，每当出现一个 'b'，我们需要检查它的“邻居”。
• 如果 'b' 的前面是 'a'，那它的后面就不能是 'c'。
• 如果 'b' 的后面是 'c'，那它的前面就不能是 'a'。
• 解答的思路是，把所有“安全”的构建块列出来，然后用星号把它们串起来。
• 安全的块:
• a: 安全。
• c: 安全。
• b: 不一定安全，取决于上下文。
• 如何让 b 变得安全？
• 如果 b 前面是 c -> cb 是安全的，因为 cb 后面跟任何东西都不会构成 "abc"。
• 如果 b 后面是 a -> ba 是安全的。
• 如果 b 后面是 b -> bb 是安全的。
• ...
• 解答将所有可能的安全组合起来：a, c, cb, ba, bb, bbb 等。
• a
• c
• ba ('b' 后面跟了个 'a')
• cb ('b' 前面跟了个 'c')
• bb (b 后面跟了个 b)
• bbb
• 把这些安全的“原子”组合起来： (a \cup c \cup ba \cup cb \cup bb \cup bbb ...)^*
• 处理b的边界情况:
• 上面的构造忽略了 b 可以出现在字符串的开头或结尾。例如，字符串 "b" 是合法的，"bc" 是合法的，"ab" 是合法的。
• 在 (a \cup cb \cup ...)^* 的构造中，b 总是被 a 或 c 或其他 b "包裹"着。
• 为了允许 b 单独出现在开头或结尾，解答在前后加上了 (\epsilon \cup b)。
• (\epsilon \cup b) 表示：开头可以有一个 b，也可以没有。结尾也可以有一个 b，也可以没有。
• 最终表达式: $(\epsilon \cup b)(a \cup cb \cup ba \cup bb \cup bbb \cup c)^{*}(\epsilon \cup b)$。
• 这个表达式非常复杂，而且 (bb \cup bbb \cup c) 似乎有误，应该是 (bb \cup bbb) 和 c 分开。正确的应该是 (a \cup c \cup ba \cup cb \cup b^+)^*，其中 $b^+$ 表示一个或多个b。解答中 bb \cup bbb 只是 $b^n, n\ge2$ 的一个不完整尝试。
• 这是一个非常tricky的题目，其解答的思路也较为晦涩和可能存在不严谨之处，理解其尝试规避"abc"的核心思想即可。

这个问题要求我们使用“通过 GNFA 消除状态”的方法，将一个 NFA 转换为等价的正则表达式。这是一个标准的算法。

算法步骤:

1. 转换为 GNFA 格式:
   • a. 添加一个新的起始状态 $s_{start}$，并从它画一条 $\epsilon$-转移到原 NFA 的起始状态。
   • b. 添加一个新的唯一接受状态 $s_{accept}$，并从所有原 NFA 的接受状态画 $\epsilon$-转移到 $s_{accept}$。
   • c. 如果两个状态之间有多条边，用并集 $\cup$ 合并它们。
   • d. 如果两个状态之间没有边，可以认为有一条用 $\emptyset$ 标记的边。
2. 依次消除状态:
   • 选择一个非 $s_{start}$ 和 $s_{accept}$ 的中间状态 $q_{rip}$ 进行消除。
   • 对于每一对状态 $(q_i, q_j)$（$q_i$ 可以是 $s_{start}$，$q_j$ 可以是 $s_{accept}$），我们需要更新从 $q_i$ 到 $q_j$ 的路径，以包含原来“经过” $q_{rip}$ 的路径。
   • 更新公式：$R_{new}(i, j) = R_{old}(i, j) \cup R(i, rip) (R(rip, rip))^* R(rip, j)$。
   • $R(i, j)$ 是从 $q_i$ 到 $q_j$ 的正则表达式标签。
   • 这个公式的含义是：从 $i$ 到 $j$ 的新路径 = 原来从 $i$ 直达 $j$ 的路径 或 (从 $i$ 到 $rip$ 的路径，接着在 $rip$ 自身循环任意次，再接着从 $rip$ 到 $j$ 的路径)。
3. 重复步骤 2，直到只剩下 $s_{start}$ 和 $s_{accept}$。此时，从 $s_{start}$ 到 $s_{accept}$ 的边上的正则表达式就是最终答案。

• 原始 NFA:
• 起始状态: $q_0$
• 接受状态: $\{q_0\}$
• 状态: $\{q_0, q_1, q_2\}$
• 转换为 GNFA 格式:

1. 新起始状态 $s$: 添加 $s$，并画一条 $\epsilon$-转移到原起始状态 $q_0$。
2. 新接受状态 $f$: 添加 $f$。原接受状态是 $q_0$，所以从 $q_0$ 画一条 $\epsilon$-转移到 $f$。
3. 合并转移:
   • 从 $q_2$ 到 $q_1$ 有两条边，分别标 '0' 和 '1'。合并为一条边，标签为 $0 \cup 1$。
4. $\epsilon$ 替换为正则表达式: $\epsilon$ 是一个合法的正则表达式。
5. 缺失的边: 比如从 $q_1$ 到 $q_1$ 没有边，可以认为标签是 $\emptyset$。
   • 得到的 GNFA 如图所示，它有 5 个状态 {$s, q_0, q_1, q_2, f$}，并准备好进行状态消除。

• 选择要消除的状态: $q_1$。
• 识别相关的路径: 我们需要找到所有“经过” $q_1$ 的路径，即形如 $q_i \to q_1 \to q_j$ 的路径。
• $q_1$ 的入边: 从 $q_2$ 来，标签是 $0 \cup 1$。
• $q_1$ 的出边: 到 $q_0$ (标签 1)，到 $q_2$ (标签 0)。
• $q_1$ 没有自循环，所以 $R(1,1) = \emptyset$，那么 $(R(1,1))^* = \epsilon$。
• 应用公式 $R_{new}(i, j) = R_{old}(i, j) \cup R(i, 1) (R(1, 1))^* R(1, j)$
• 路径 $q_2 \to q_1 \to q_0$:
• $i=2, j=0, rip=1$。
• $R_{new}(2,0) = R_{old}(2,0) \cup R(2,1) (\epsilon) R(1,0)$
• $R_{old}(2,0) = \emptyset$ (原来 $q_2$ 到 $q_0$ 没有直达边)。
• $R(2,1) = 0 \cup 1$。
• $R(1,0) = 1$。
• 所以 $R_{new}(2,0) = \emptyset \cup (0 \cup 1) \cdot \epsilon \cdot 1 = (0 \cup 1)1 = 01 \cup 11$。
• 于是在新图中，我们从 $q_2$ 到 $q_0$ 画一条标签为 $01 \cup 11$ 的边。
• 路径 $q_2 \to q_1 \to q_2$:
• $i=2, j=2, rip=1$。
• $R_{new}(2,2) = R_{old}(2,2) \cup R(2,1) (\epsilon) R(1,2)$
• $R_{old}(2,2) = \emptyset$ (原来 $q_2$ 没有自循环)。
• $R(2,1) = 0 \cup 1$。
• $R(1,2) = 0$。
• 所以 $R_{new}(2,2) = \emptyset \cup (0 \cup 1) \cdot \epsilon \cdot 0 = (0 \cup 1)0 = 00 \cup 10$。
• 于是在新图中，$q_2$ 获得了一个自循环，标签为 $00 \cup 10$。
• 消除 $q_1$ 后，将这些新计算出的边画入图中，得到一个 4 状态的 GNFA。

• 选择要消除的状态: $q_2$。
• 识别相关的路径:
• $q_2$ 的入边: 从 $q_0$ 来，标签是 $0$。
• $q_2$ 的出边: 到 $q_0$ (标签 $01 \cup 11$)，到 $f$ (标签 $\epsilon$)。
• $q_2$ 有自循环: 标签是 $00 \cup 10$。所以 $R(2,2) = 00 \cup 10$。
• 应用公式更新路径:
• 路径 $q_0 \to q_2 \to f$:
• $i=0, j=f, rip=2$。
• $R_{new}(0,f) = R_{old}(0,f) \cup R(0,2) (R(2,2))^* R(2,f)$
• $R_{old}(0,f) = \epsilon$ (原来 $q_0$ 到 $f$ 的直达边)。
• $R(0,2) = 0$。
• $(R(2,2))^* = (00 \cup 10)^*$。
• $R(2,f) = \epsilon$。
• 所以 $R_{new}(0,f) = \epsilon \cup 0(00 \cup 10)^*\epsilon = \epsilon \cup 0(00 \cup 10)^*$。
• 注意: 解答中似乎将这一步与下一步合并了，或者顺序不同。让我们严格按照图示的更新结果来反推。图中从 $q_0$ 到 $f$ 的新边是 $0(00 \cup 10)^*$。这说明它只计算了经过 $q_2$ 的那部分 $R(0,2)(R(2,2))^*R(2,f)$，并将其作为一条新的平行边添加，而不是与旧的 $\epsilon$ 边合并。这在算法执行中也是可以的，最后再合并平行边。
• 路径 $q_0 \to q_2 \to q_0$:
• $i=0, j=0, rip=2$。
• $R_{new}(0,0) = R_{old}(0,0) \cup R(0,2) (R(2,2))^* R(2,0)$
• $R_{old}(0,0) = 1$ (原来 $q_0$ 的自循环)。
• $R(0,2) = 0$。
• $(R(2,2))^* = (00 \cup 10)^*$。
• $R(2,0) = 01 \cup 11$。
• 所以 $R_{new}(0,0) = 1 \cup 0(00 \cup 10)^*(01 \cup 11)$。
• 这更新了 $q_0$ 的自循环的标签。
• 消除 $q_2$ 后，剩下 $s, q_0, f$ 三个状态。
• $s \xrightarrow{\epsilon} q_0$。
• $q_0$ 有一个自循环，标签为 $1 \cup 0(00 \cup 10)^*(01 \cup 11)$。
• 从 $q_0$ 到 $f$ 有两条边：一条是原来的 $\epsilon$，一条是新加的 $0(00 \cup 10)^*$。我们可以将它们合并为 $\epsilon \cup 0(00 \cup 10)^*$。
• 再次注意：解答的图中，从 $q_0$到 $f$ 只画了一条边，标签是 $0(00 \cup 10)^*$。它似乎在这里犯了一个错误，遗漏了原来从 $q_0$ 到 $f$ 的 $\epsilon$ 边。这个遗漏会影响最终结果。让我们暂时跟着它的错误计算下去。

• 选择要消除的状态: $q_0$。
• 识别相关的路径: 只有一条路径需要计算，就是 $s \to q_0 \to f$。
• 应用公式:
• $i=s, j=f, rip=0$。
• $R_{new}(s,f) = R_{old}(s,f) \cup R(s,0) (R(0,0))^* R(0,f)$。
• $R_{old}(s,f) = \emptyset$ (s 和 f 原来不直连)。
• $R(s,0) = \epsilon$。
• $(R(0,0))^* = (1 \cup 0(00 \cup 10)^*(01 \cup 11))^*$。
• $R(0,f) = 0(00 \cup 10)^*$ (这里我们使用了解答上一步中那条可能错误的边)。
• 所以 $R_{new}(s,f) = \epsilon (1 \cup 0(00 \cup 10)^*(01 \cup 11))^* 0(00 \cup 10)^*$。
• 最终表达式: $(1 \cup 0(00 \cup 10)^*(01 \cup 11))^* 0(00 \cup 10)^*$。

如果我们修正上一步的错误:

• 如果上一步从 $q_0$ 到 $f$ 的边是 $\epsilon \cup 0(00 \cup 10)^*$。
• 那么 $R(0,f) = \epsilon \cup 0(00 \cup 10)^*$。
• 最终表达式会变成: $\epsilon (1 \cup 0(00 \cup 10)^*(01 \cup 11))^* (\epsilon \cup 0(00 \cup 10)^*)$。
• 这个表达式更复杂，但它和解答给出的表达式描述的是不同的语言。解答的版本不接受 $\epsilon$，而修正后的版本接受 $\epsilon$。
• 原始 NFA 的起始状态 $q_0$ 是接受状态，所以它接受 $\epsilon$。因此，正确的正则表达式必须能生成 $\epsilon$。
• 结论: 解答在第 3 步中犯了一个错误，导致最终的正则表达式是错误的，它丢失了对 $\epsilon$ 和其他一些字符串的识别能力。

这个问题要求我们将一个复杂的正则表达式通过标准的递归构造方法（汤普森构造法）转换为一个 NFA。这种方法不追求状态最少，但保证了过程的机械化和正确性。

正则表达式: $(01)^*(10^* \cup 0)$

分解与构造:

第一部分：构造识别 $(01)^*$ 的 NFA ($N_1$)

• 1a. 构造 01: 这是连接。
• 构造 0: $s_0 \xrightarrow{0} s_1$ ($s_1$ 接受)。
• 构造 1: $s_2 \xrightarrow{1} s_3$ ($s_3$ 接受)。
• 连接它们：从 $s_1$ (0的接受状态) 画 $\epsilon$-转移到 $s_2$ (1的起始状态)，并取消 $s_1$ 的接受状态。最终得到 $s_0 \xrightarrow{0} s_1 \xrightarrow{\epsilon} s_2 \xrightarrow{1} s_3$。可以简化为 $q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2$。
• 1b. 构造 (01)^* (星号运算):
• 取上面 01 的 NFA ($q_0 \to q_1 \to q_2$)。
• 1. 添加新起始状态 $s_{new}$，并设为接受状态。
• 2. 添加 $\epsilon$-转移: $s_{new} \to q_0$ (进入循环)。
• 3. 添加 $\epsilon$-转移: $q_2 \to s_{new}$ (完成一次并返回)。
• 解答中的图示采用了另一种等价的星号构造方法：(1) 添加新起始/接受状态 $s$ (2) 添加 $s \xrightarrow{\epsilon} q_0$ (3) 添加 $q_2 \xrightarrow{\epsilon} s$ (4) 添加 $q_2 \xrightarrow{\epsilon} q_0$ 的返回边和 $s$ 成为接受状态。解答中的图更复杂，但核心思想都是为了实现“0次或多次重复”。

第二部分：构造识别 $(10^* \cup 0)$ 的 NFA ($N_2$)

• 这是一个并集，所以我们先构造两部分，再合并。
• 2a. 构造 10*:
• 构造 1: $p_0 \xrightarrow{1} p_1$。
• 构造 0*: (使用星号构造) $p_2 \xrightarrow{\epsilon} p_3 \xrightarrow{0} p_3 \xrightarrow{\epsilon} p_4$，$p_2,p_4$ 是接受状态。
• 连接它们：$p_1$ (1的接受状态) $\epsilon$-转移到 $p_2$ (0*的起始状态)。$p_1$ 不再是接受状态。最终接受状态是 $p_4$。
• 解答的图示简化了这个过程，直接画出：$p_0 \xrightarrow{1} p_1$，然后 $p_1$ 上有一个 '0' 的自循环。这在直觉上更简单，也是对 0* 的一种有效表达。所以得到 $p_0 \xrightarrow{1} p_1(\text{自循环}0)$，$p_1$ 是接受。
• 2b. 构造 0: 很简单，$p_5 \xrightarrow{0} p_6$ ($p_6$ 接受)。
• 2c. 构造 (10* \cup 0) (并集运算):
• 取上面 10* 的 NFA 和 0 的 NFA。
• 添加新起始状态 $s_{union}$。
• 从 $s_{union}$ 分别画 $\epsilon$-转移到它们的原起始状态（$p_0$ 和 $p_5$）。
• 保留它们原来的接受状态（$p_1$ 和 $p_6$）。

第三部分：构造最终 NFA (连接运算)

• 我们现在有两个 NFA：$N_1$ 识别 $(01)^*$，$N_2$ 识别 $(10^* \cup 0)$。
• 要构造 $N_1N_2$ 的 NFA。
• 连接:

1. 取 $N_1$ 的所有接受状态。在步骤 1b 的图中，是 $\{s, q_2\}$。
2. 从这每一个接受状态画 $\epsilon$-转移到 $N_2$ 的起始状态 $s_{union}$。
3. 取消 $N_1$ 的接受状态资格。它们现在是中转站。
4. $N_1$ 的起始状态（$s$）成为最终 NFA 的起始状态。
5. $N_2$ 的接受状态（$\{p_1, p_6\}$）成为最终 NFA 的接受状态。
   • 最终得到的那个巨大的、有很多 $\epsilon$-转移的图，就是严格按照构造规则生成的 NFA。

这份讲义的解答集全面地涵盖了计算理论中关于正规语言的几个核心支柱。通过一系列具体的问题和详尽的解答，它强化了以下关键概念：

1. NFA 的设计与理解：我们学习了如何构造 NFA 来识别特定的语言。关键在于利用非确定性（一个状态在同一输入下可以有多个后续状态）和 $\epsilon$-转移（不消耗输入即可切换状态）来简化设计。例如，识别“包含子串 101”或满足“条件A或条件B”的语言时，NFA 的“猜测”和“并行宇宙”能力使其构造比等价的 DFA 更为直观和简洁。
2. NFA 到 DFA 的转换：通过子集构造法，我们掌握了将任何 NFA（包括带 $\epsilon$-转移的）机械化地转换为一个等价 DFA 的标准算法。这个过程不仅是一个重要的实践技能，更是在理论上证明了 NFA 和 DFA 的表达能力是完全等价的——它们都只能识别正规语言，不多也不少。DFA 的每一个状态都对应着 NFA 可能处于的一个状态子集。
3. 正规语言的封闭性质：讲义通过构造性证明，生动地展示了正规语言在多种运算下是封闭的。这意味着对正规语言进行这些运算后，结果仍然是正规语言。我们实践了以下构造：
   • 并集 ($L_1 \cup L_2$): 创建一个新起始状态，通过 $\epsilon$-转移连接到两个旧自动机的起始状态。
   • 连接 ($L_1 L_2$): 将第一个自动机的接受状态通过 $\epsilon$-转移连接到第二个自动机的起始状态。
   • 克莱尼星号 ($L^*$): 创建一个既是起始状态又是接受状态的新枢纽状态，通过 $\epsilon$-转移实现进入、退出和循环。
   • 逆转 ($L^R$): 反转所有转移箭头，并巧妙地交换起始状态和接受状态的角色。
   • 自定义运算 ($\min(L)$): 修改 DFA，使任何计算路径在第一次到达接受状态后便“锁死”，无法继续匹配更长的字符串。
4. 正则表达式的诠释与构造：我们练习了如何将语言的文字描述翻译成正则表达式，以及反向地用自然语言描述一个给定的正则表达式。这需要将语言的性质分解为由连接、并集 ($\cup$) 和星号 ($*$) 等基本部分组成的结构。
5. 不同表示模型的等价性与转换：这是本讲义的核心。它通过两个方向的算法实践，强化了有限自动机和正则表达式的等价性：
   • NFA 到正则表达式: 使用“通过 GNFA 消除状态”的方法，通过迭代地移除状态并更新边上的正则表达式，最终得到一个单一的表达式。
   • 正则表达式到 NFA: 使用“汤普森构造法”，自底向上地为正则表达式的每个部分（原子、并集、连接、星号）构建对应的 NFA 模块，然后像搭积木一样将它们拼接起来。

这些算法是计算理论的基石，并且在编译器设计、文本搜索工具（如 grep）、网络协议分析等领域有着广泛的实际应用。