1 COMS 3261 讲义 6A：NFA 和 正则表达式 练习

这部分是讲义的标题和作者信息。它明确了这份学习资料的主题、作者以及适用的学期。

• COMS 3261：这是课程代码，通常代表一门具体的大学课程。在这里，它指向哥伦比亚大学的“计算机科学理论”课程。
• 讲义 6A：这表明是系列讲义中的第六部分，A可能表示这是练习部分（通常B是解答部分）。
• NFA 和 正则表达式 练习：这直接点明了本讲义的核心内容，即非确定性有限自动机（NFA）和正则表达式（Regular Expressions）的相关练习题。这两者是计算理论中描述正则语言的两个核心工具。
• Kiru Arjunan 和 Ziheng Huang：讲义的编写者。
• 2024年秋季：讲义发布或适用的时间。

本节开始进入非确定性有限自动机（NFA）的具体练习。NFA是计算模型的一种，用于识别（或“接受”）特定模式的字符串集合，即语言。与确定性有限自动机（DFA）不同，NFA在某个状态下，对于一个输入符号，可以有零个、一个或多个转移路径，还可以有不需要任何输入符号就能进行的ε-转移（空转移）。

我们要构造一个NFA，它能“记住”是否已经看到了子串“101”。NFA的非确定性特性在这里非常有用，我们可以让它“猜测”子串“101”何时开始。

1. 起始状态 $q_0$：这是我们的起点。在找到“101”之前，我们一直停留在这个“寻找”阶段。任何不属于我们目标子串开头的字符（0或1）都应该让我们继续寻找。所以，在$q_0$上有一个自循环，接受0和1。这代表“我还没开始匹配‘101’，请继续输入”。
2. 寻找第一个‘1’：当我们在$q_0$时，如果输入是‘1’，我们可能开始了一个“101”序列。NFA允许我们同时探索两条路：一条是留在$q_0$（因为这个‘1’可能不是“101”的开头），另一条是转移到一个新状态$q_1$，表示“我可能找到了‘101’的第一个字符‘1’”。
3. 寻找‘0’：在状态$q_1$时，我们期望下一个字符是‘0’。如果输入是‘0’，我们就转移到状态$q_2$。这表示“我连续找到了‘1’和‘0’”。如果输入是‘1’，那我们匹配失败了，这条路径就“死”了（没有定义转移）。
4. 寻找第二个‘1’：在状态$q_2$时，我们期望下一个字符是‘1’。如果输入是‘1’，我们就转移到最终状态$q_3$。这表示“我成功找到了子串‘101’！”。如果输入是‘0’，匹配失败，路径死亡。
5. 接受状态 $q_3$：一旦到达$q_3$，说明字符串中已经包含了“101”。之后无论再输入什么（0或1），我们都应该接受这个字符串。所以在$q_3$上有一个自循环，接受0和1。

NFA状态图如下：

• $q_0$：起始状态。
• $q_0 \xrightarrow{0,1} q_0$
• $q_0 \xrightarrow{1} q_1$
• $q_1 \xrightarrow{0} q_2$
• $q_2 \xrightarrow{1} q_3$
• $q_3$：接受状态。
• $q_3 \xrightarrow{0,1} q_3$

这个语言是两个子语言的并集：

• $L_1 = \{w \mid w \text{ 恰好有两个 0}\}$
• $L_2 = \{w \mid w \text{ 有偶数个 1}\}$

根据正则语言对并运算的封闭性，我们可以分别为 $L_1$ 和 $L_2$ 构造自动机，然后使用并的构造方法将它们组合起来。NFA的并构造非常简单：创建一个新的起始状态，然后用 ε-转移（空转移）连接到原来两个自动机的起始状态。

1. 构造识别 $L_1$ (恰好有两个 0) 的 NFA (实际上是DFA):

我们需要计数字符串中 0 的数量。

• $c_0$: 起始状态，表示有0个'0'。
• $c_1$: 表示有1个'0'。
• $c_2$: 表示有2个'0'。这是接受状态。
• $c_3$: “陷阱”状态，表示有超过2个'0'。

转移如下：

• $c_0 \xrightarrow{0} c_1$, $c_0 \xrightarrow{1} c_0$
• $c_1 \xrightarrow{0} c_2$, $c_1 \xrightarrow{1} c_1$
• $c_2 \xrightarrow{0} c_3$, $c_2 \xrightarrow{1} c_2$ (在 $c_2$ 读到'1's不改变0的计数)
• $c_3 \xrightarrow{0,1} c_3$

2. 构造识别 $L_2$ (偶数个 1) 的 NFA (实际上是DFA):

我们需要计数 1 的数量是奇数还是偶数。

• $e_0$: 起始状态，表示有偶数个'1' (0是偶数)。这是接受状态。
• $e_1$: 表示有奇数个'1'。

转移如下：

• $e_0 \xrightarrow{1} e_1$, $e_0 \xrightarrow{0} e_0$
• $e_1 \xrightarrow{1} e_0$, $e_1 \xrightarrow{0} e_1$

3. 组合成最终的 NFA:

• 创建一个新的起始状态 $q_{start}$。
• 从 $q_{start}$ 添加两条 ε-转移：
• $q_{start} \xrightarrow{\epsilon} c_0$ (连接到 $L_1$ 的起始状态)
• $q_{start} \xrightarrow{\epsilon} e_0$ (连接到 $L_2$ 的起始状态)
• 所有原来是接受状态的，现在仍然是接受状态。所以接受状态集合是 $\{c_2, e_0\}$。

这个组合起来的 NFA 有7个状态 ($q_{start}, c_0, c_1, c_2, c_3, e_0, e_1$)。当一个字符串输入时，NFA会“猜测”这个字符串应该满足哪个条件（有两个0还是偶数个1），然后进入相应的子自动机进行验证。

这一节要求我们反向工程：给定一个NFA的状态图，我们要推断出它所接受的语言，并用自然语言或集合符号来描述。

我们来分析这个NFA的行为：

1. 状态: 有三个状态，我们标记为 $q_0, q_1, q_2$。
   • $q_0$: 起始状态（由一个指向它的、没有来源的箭头指示）。
   • $q_2$: 接受状态（由双层圆圈指示）。
2. 转移:
   • $q_0 \xrightarrow{0,1} q_0$: 在起始状态，任何输入（0或1）都可以让它停留在原地。这表示在匹配到关键模式之前，可以有任意的前缀。
   • $q_0 \xrightarrow{0} q_1$: 当输入为'0'时，除了停留在$q_0$，还可以选择进入$q_1$。这像是在说：“嘿，这可能是一个关键模式的开始。”
   • $q_1 \xrightarrow{0} q_2$: 从$q_1$状态，如果再输入一个'0'，就可以进入接受状态$q_2$。这表明，连续的两个'0'（即子串"00"）是通往接受的关键。
   • $q_2 \xrightarrow{0,1} q_2$: 一旦进入接受状态$q_2$，任何后续的输入（0或1）都会让它停留在$q_2$。这意味着一旦字符串中出现了"00"，无论后面跟什么，整个字符串都会被接受。

综合分析:

• 要想到达接受状态$q_2$，必须经过路径 $q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2$。
• 这要求输入字符串中必须包含一个子串"00"。
• 在"00"出现之前，可以在$q_0$上消耗任意的0和1（对应正则表达式 $(0 \cup 1)^{*}$）。
• 在"00"出现之后，可以在$q_2$上消耗任意的0和1（对应正则表达式 $(0 \cup 1)^{*}$）。

所以，这个NFA接受的语言是所有包含子串"00"的二进制字符串。用正则表达式表示就是 $(0 \cup 1)^{*}00(0 \cup 1)^{*}$。

我们来分析这个更复杂的NFA：

1. 状态: 有五个状态，我们标记为 $q_0, q_1, q_2, q_3, q_4$。
   • $q_0$: 起始状态。它也是一个接受状态，这意味着空字符串$\epsilon$被接受。
   • $q_2, q_4$: 另外两个接受状态。
2. 转移:
   • 从 $q_0$ 出发:
   • $q_0 \xrightarrow{0} q_1$: “猜测”字符串以'0'开头。
   • $q_0 \xrightarrow{1} q_3$: “猜测”字符串以'1'开头。
   • 因为$q_0$本身是接受状态，这处理了空字符串$\epsilon$的情况。
   • "0"路径:
   • $q_1 \xrightarrow{0,1} q_1$: 一旦以'0'开头，中间可以有任意多个0和1。
   • $q_1 \xrightarrow{0} q_2$: 当以'0'结尾时，可以进入接受状态$q_2$。
   • "1"路径:
   • $q_3 \xrightarrow{0,1} q_3$: 一旦以'1'开头，中间可以有任意多个0和1。
   • $q_3 \xrightarrow{1} q_4$: 当以'1'结尾时，可以进入接受状态$q_4$。

综合分析:

这个NFA的结构明显分成了两大赛道：

• 空字符串: 起始状态$q_0$就是接受状态，所以空字符串 $\epsilon$ 被接受。
• 以0开头的路径: 从$q_0$经过$q_1$到$q_2$。这条路径要求第一个字符是'0'。中间经过$q_1$的自循环，可以有任意字符。最后要想到达接受状态$q_2$，必须以'0'结尾。所以这条路径接受的语言是“以0开头且以0结尾的非空字符串”。
• 以1开头的路径: 从$q_0$经过$q_3$到$q_4$。这条路径要求第一个字符是'1'。中间经过$q_3$的自循环，可以有任意字符。最后要想到达接受状态$q_4$，必须以'1'结尾。所以这条路径接受的语言是“以1开头且以1结尾的非空字符串”。

结论: 将这三种情况合并：

1. 空字符串 $\epsilon$。
2. 以0开头且以0结尾的非空字符串。
3. 以1开头且以1结尾的非空字符串。

这可以统一描述为：所有首尾字符相同的二进制字符串，以及空字符串。

我们还可以考虑单字符字符串：

• "0": $q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2$ (路径不成立)。但是， $q_0 \xrightarrow{0} q_1$ 是合法的，但是$q_1$不是接受状态。这里的设计有些微妙。让我们重新审视一下 $q_1 \xrightarrow{0} q_2$。这意味着要想到达$q_2$，字符串至少要长为2。
• Let's re-trace "0": $q_0 \xrightarrow{0} q_1$. 字符串结束， $q_1$不是接受态。不接受。
• Let's re-trace "00": $q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2$. 字符串结束， $q_2$是接受态。接受。
• Let's re-trace "1": $q_0 \xrightarrow{1} q_3$. 字符串结束，不接受。
• Let's re-trace "11": $q_0 \xrightarrow{1} q_3 \xrightarrow{1} q_4$. 字符串结束，接受。

所以，这个NFA接受的语言是：

• 空字符串 $\epsilon$。
• 所有长度大于等于2的，首尾字符相同的字符串。

这与通常理解的“首尾字符相同”（包含单字符 "0", "1"）略有不同。我们必须严格按照自动机的定义来。

让我们检查一下，也许单字符可以被接受？

• "0": 从 $q_0$ 读 '0'，只能到 $q_1$。$q_1$不是接受态。所以 "0" 不被接受。
• "1": 从 $q_0$ 读 '1'，只能到 $q_3$。$q_3$不是接受态。所以 "1" 不被接受。

因此，最终结论是：该语言是空字符串 $\epsilon$ ，以及所有长度至少为2且首字符和尾字符相同的二进制字符串。

用集合表示为：

$L = \{\epsilon\} \cup \{w \in \{0,1\}^* \mid |w| \ge 2 \text{ and } w \text{ starts and ends with '0'}\} \cup \{w \in \{0,1\}^* \mid |w| \ge 2 \text{ and } w \text{ starts and ends with '1'}\}$

或者更简洁地: $L = \{\epsilon\} \cup \{0w0 \mid w \in \{0,1\}^*\} \cup \{1w1 \mid w \in \{0,1\}^*\}$

子集构造法（Subset Construction）是一种标准的算法，用于将一个NFA转换为一个等价的DFA。其核心思想是，DFA的每一个状态都对应于NFA中可能处于的状态的集合（子集）。

让我们把给定的NFA状态标记为：状态1和状态2。

• NFA状态: $N = \{1, 2\}$。
• 字母表: $\Sigma = \{a, b\}$。
• NFA起始状态: $q_{start\_NFA} = \{1\}$。
• NFA接受状态: $F_{NFA} = \{2\}$。
• NFA转移函数 $\delta_N$:
• $\delta_N(1, a) = \{1, 2\}$
• $\delta_N(1, b) = \{2\}$
• $\delta_N(2, a) = \emptyset$ (空集)
• $\delta_N(2, b) = \{1, 2\}$
• 这个NFA没有 ε-转移，所以我们不需要计算 ε-闭包。

构造 DFA 步骤:

1. DFA 的起始状态: DFA的起始状态是NFA起始状态所在的集合。这里就是 $\{1\}$。我们把这个新的DFA状态命名为 $S_0 = \{1\}$。
2. 探索 $S_0 = \{1\}$:
   • 输入 'a': 我们需要计算从 $S_0$ 中的每个NFA状态出发，经过 'a' 能到达的所有NFA状态的并集。
   • $ \delta_D(S_0, a) = \delta_N(1, a) = \{1, 2\} $
   • 这是一个新的DFA状态。我们命名为 $S_1 = \{1, 2\}$。
   • 输入 'b':
   • $ \delta_D(S_0, b) = \delta_N(1, b) = \{2\} $
   • 这是一个新的DFA状态。我们命名为 $S_2 = \{2\}$。
3. 探索 $S_1 = \{1, 2\}$:
   • 输入 'a':
   • $ \delta_D(S_1, a) = \delta_N(1, a) \cup \delta_N(2, a) = \{1, 2\} \cup \emptyset = \{1, 2\} $
   • 这个状态我们已经见过了，就是 $S_1$。所以 $S_1 \xrightarrow{a} S_1$。
   • 输入 'b':
   • $ \delta_D(S_1, b) = \delta_N(1, b) \cup \delta_N(2, b) = \{2\} \cup \{1, 2\} = \{1, 2\} $
   • 这个状态也是 $S_1$。所以 $S_1 \xrightarrow{b} S_1$。
4. 探索 $S_2 = \{2\}$:
   • 输入 'a':
   • $ \delta_D(S_2, a) = \delta_N(2, a) = \emptyset $
   • 这是一个新的DFA状态，即空集状态。我们命名为 $S_3 = \emptyset$。这是一个“陷阱”状态。
   • 输入 'b':
   • $ \delta_D(S_2, b) = \delta_N(2, b) = \{1, 2\} $
   • 这个状态是 $S_1$。所以 $S_2 \xrightarrow{b} S_1$。
5. 探索 $S_3 = \emptyset$:
   • 输入 'a':
   • $ \delta_D(S_3, a) = \emptyset $
   • 它自己转移到自己。$S_3 \xrightarrow{a} S_3$。
   • 输入 'b':
   • $ \delta_D(S_3, b) = \emptyset $
   • 它自己转移到自己。$S_3 \xrightarrow{b} S_3$。

整合 DFA:

• DFA 状态集: $Q_D = \{S_0, S_1, S_2, S_3\}$，其中 $S_0=\{1\}, S_1=\{1,2\}, S_2=\{2\}, S_3=\emptyset$。
• DFA 起始状态: $S_0 = \{1\}$。
• DFA 接受状态: DFA的接受状态是所有那些包含了NFA接受状态的集合。NFA的接受状态是 $\{2\}$。所以，任何包含状态'2'的DFA状态都是接受状态。
• $S_1 = \{1, 2\}$ 包含 '2'，是接受状态。
• $S_2 = \{2\}$ 包含 '2'，是接受状态。
• $F_D = \{S_1, S_2\}$。

DFA 转移表:

画出 DFA 状态图:

• 画出四个圈，分别标记为 $S_0, S_1, S_2, S_3$。
• $S_0$ 是起始状态（画一个无源箭头指向它）。
• $S_1$ 和 $S_2$ 是接受状态（画成双层圆圈）。
• 根据上表连接箭头：
• $S_0 \xrightarrow{a} S_1$
• $S_0 \xrightarrow{b} S_2$
• $S_1 \xrightarrow{a} S_1$ (自循环)
• $S_1 \xrightarrow{b} S_1$ (自循环)
• $S_2 \xrightarrow{a} S_3$
• $S_2 \xrightarrow{b} S_1$
• $S_3 \xrightarrow{a} S_3$ (自循环)
• $S_3 \xrightarrow{b} S_3$ (自循环)

本节的引言部分，总结了课程已经讲过的内容，并预告了接下来要讨论的新内容。

• 正则语言类：指的是所有可以被有限自动机（DFA或NFA）识别的语言的集合。
• 封闭性（Closure Property）：一个集合在一个运算下是封闭的，意味着从该集合中取出任意一个或两个元素进行该运算，得到的结果仍然在该集合内。
• 例如，整数集合在加法下是封闭的，因为任意两个整数相加，结果还是整数。但整数集合在除法下不封闭（例如 3 / 2 = 1.5，不是整数）。
• 已学内容回顾：

1. 使用 NFA 证明了正则语言在以下三个基本正则运算下是封闭的：
   • 并 (Union, $\cup$): $L_1 \cup L_2$
   • 连接 (Concatenation, $\circ$): $L_1 \circ L_2$
   • 克林星号 (Kleene Star, $*$): $L_1^*$
2. 之前使用 DFA 证明了正则语言在以下布尔运算下是封闭的：
   • 补 (Complement, $\overline{L}$): 通过将DFA的接受状态和非接受状态互换得到。
   • 交 (Intersection, $\cap$): 通过乘积构造（Product Construction）得到。
   • 并 (Union, $\cup$): 也可以通过乘积构造，或者利用德摩根定律 $\overline{(\overline{L_1} \cap \overline{L_2})}$。
   • 本节目标：
   • 简要回顾已学的并、连接、星号的NFA构造。
   • 证明正则语言在一些其他运算下也是封闭的，包括：
   • 逆转 (Reversal, $L^R$)
   • min(L)
   • max(L) (虽然这里写了，但后面问题里没出现，可能是笔误或计划在别处讲)
   • 对称差 (Symmetric Difference)

这部分回顾了为两个正则语言 $L_1$ 和 $L_2$ 的并集 $L_1 \cup L_2$ 构造NFA的标准方法。

假设我们已经有了识别 $L_1$ 的NFA $N_1$ 和识别 $L_2$ 的NFA $N_2$。

1. 图片分析:
   • 第一张图是一个抽象的NFA $N_1$，它有一个起始状态和一些接受状态，识别语言 $L_1$。
   • 第二张图是另一个抽象的NFA $N_2$，识别语言 $L_2$。
   • 第三张图展示了构造 $L_1 \cup L_2$ 的NFA $N$ 的过程。
2. 构造步骤:
   • 不改变原有机器: 保持 $N_1$ 和 $N_2$ 的内部结构完全不变。
   • 添加新起始状态: 创建一个全新的状态，作为新NFA $N$ 的唯一起始状态，我们称之为 $q_{new\_start}$。
   • 添加ε-转移: 从 $q_{new\_start}$ 画两条ε-转移（不消耗任何输入符号的转移）：一条指向 $N_1$ 的原起始状态，另一条指向 $N_2$ 的原起始状态。
   • 接受状态: $N$ 的接受状态集合是 $N_1$ 和 $N_2$ 所有接受状态的并集。
3. 工作原理:

当一个新的字符串输入到 $N$ 时，它首先从 $q_{new\_start}$ 开始。由于有ε-转移，NFA会立即、不消耗任何输入地“分裂”成两个并行的计算路径：一个进入了 $N_1$ 的起始点，另一个进入了 $N_2$ 的起始点。

• 接下来，整个字符串会在这两条路径上（在 $N_1$ 和 $N_2$ 内部）并行地进行处理。
• 如果字符串走完后，在 $N_1$ 内部的路径到达了 $N_1$ 的一个接受状态，那么整个字符串就被 $N$ 接受。
• 或者，如果字符串在 $N_2$ 内部的路径到达了 $N_2$ 的一个接受状态，整个字符串也被 $N$ 接受。
• 这正好对应了并集的定义：一个字符串属于 $L_1 \cup L_2$，当且仅当它属于 $L_1$ 或者 属于 $L_2$。

这个问题要求我们应用刚刚回顾的并构造法。语言 $L$ 是两个子语言 $L_1$ 和 $L_2$ 的并集。

• $L_1 = \{w \in \{0,1\}^* \mid w \text{ 有偶数个 0}\}$
• $L_2 = \{w \in \{0,1\}^* \mid w \text{ 没有两个连续的 1's}\}$

第一步：为 $L_1$ 构造 DFA

我们需要一个DFA来记录0的个数的奇偶性。

• 状态 $E_0$: 偶数个0（起始状态，接受状态）。
• 状态 $O_0$: 奇数个0。
• 转移:
• $E_0 \xrightarrow{0} O_0$
• $E_0 \xrightarrow{1} E_0$ (1不改变0的奇偶性)
• $O_0 \xrightarrow{0} E_0$
• $O_0 \xrightarrow{1} O_0$ (1不改变0的奇偶性)
• 起始状态: $E_0$。
• 接受状态: $\{E_0\}$。

第二步：为 $L_2$ 构造 DFA

我们需要一个DFA来检测是否出现了 "11"。

• 状态 $S$: 起始状态，没有连续的1（接受状态）。
• 状态 $S_1$: 刚刚看到了一个1（接受状态）。
• 状态 $D$: "Dead" 状态，已经看到了 "11"（非接受状态）。
• 转移:
• $S \xrightarrow{0} S$
• $S \xrightarrow{1} S_1$
• $S_1 \xrightarrow{0} S$ (连续1被打断)
• $S_1 \xrightarrow{1} D$ (出现 "11")
• $D \xrightarrow{0,1} D$ (一旦出现 "11"，永远陷在这里)
• 起始状态: $S$。
• 接受状态: $\{S, S_1\}$。

第三步：使用并构造法组合成 NFA

• 创建新起始状态: $q_{start}$。
• 添加 ε-转移:
• $q_{start} \xrightarrow{\epsilon} E_0$ (连接到 $L_1$ 的 DFA 起始状态)
• $q_{start} \xrightarrow{\epsilon} S$ (连接到 $L_2$ 的 DFA 起始状态)
• 整合状态: 整个NFA的状态集是 $\{q_{start}, E_0, O_0, S, S_1, D\}$。
• 整合接受状态: 新NFA的接受状态是原来两个DFA接受状态的并集，即 $\{E_0, S, S_1\}$。

画出最终的 NFA:

1. 在左边画一个新状态 $q_{start}$，并标记为起始状态。
2. 画出 $L_1$ 的两状态DFA ($E_0, O_0$)，其中 $E_0$ 是双圈。
3. 画出 $L_2$ 的三状态DFA ($S, S_1, D$)，其中 $S$ 和 $S_1$ 是双圈。
4. 从 $q_{start}$ 画一条带 $\epsilon$ 标签的箭头指向 $E_0$。
5. 从 $q_{start}$ 画另一条带 $\epsilon$ 标签的箭头指向 $S$。

这部分回顾了为两个正则语言 $L_1$ 和 $L_2$ 的连接 $L_1 \circ L_2$ 构造NFA的标准方法。连接操作指的是将 $L_1$ 中的一个字符串和 $L_2$ 中的一个字符串拼接起来，形成一个新的字符串。

假设我们已经有了识别 $L_1$ 的NFA $N_1$ 和识别 $L_2$ 的NFA $N_2$。

1. 图片分析:
   • 第一张图是识别 $L_1$ 的NFA $N_1$。
   • 第二张图是识别 $L_2$ 的NFA $N_2$。
   • 第三张图展示了构造 $L_1 \circ L_2$ 的NFA $N$ 的过程。
2. 构造步骤:
   • 保持机器: 保持 $N_1$ 和 $N_2$ 的内部结构不变。
   • 连接桥梁: 从 $N_1$ 的每一个接受状态画一条ε-转移到 $N_2$ 的起始状态。
   • 新起始状态: 新NFA $N$ 的起始状态就是 $N_1$ 的原起始状态。
   • 新接受状态: 新NFA $N$ 的接受状态就是 $N_2$ 的原接受状态。$N_1$ 的原接受状态在新的机器中不再是接受状态了（除非$N_2$能接受空串$\epsilon$）。
3. 工作原理:

一个输入字符串 $w$ 要被这个新NFA接受，它必须能被分解为两部分 $w = xy$，其中 $x$ 被 $N_1$ 接受，而 $y$ 被 $N_2$ 接受。

• 字符串的前半部分 $x$ 会驱动机器从 $N_1$ 的起始状态走到 $N_1$ 的某个接受状态。
• 到达 $N_1$ 的接受状态后，机器通过ε-转移（不消耗任何输入）“跳”到 $N_2$ 的起始状态。
• 接着，字符串的后半部分 $y$ 会驱动机器从 $N_2$ 的起始状态走到 $N_2$ 的某个接受状态。
• 因为最终停在了 $N_2$ 的接受状态，也就是新NFA的接受状态，所以整个字符串 $w=xy$ 被接受。

此题要求我们先为$L_1$和$L_2$分别构造NFA，然后应用连接构造法得到识别 $L_1 \circ L_2$ 的NFA。

第一步：为 $L_1$ 构造 NFA

$L_1$ 本身是一个并集：$L_{1a} = \{w \mid w \text{ 有奇数个 } 1's\}$ 和 $L_{1b} = \{w \mid w \text{ 恰好有两个 } 0\}$。我们可以使用并构造法来创建 $L_1$ 的NFA。

• 构造 $L_{1a}$ (奇数个 1) 的 DFA:
• $E_1$: 偶数个1 (起始状态)。
• $O_1$: 奇数个1 (接受状态)。
• $E_1 \xrightarrow{1} O_1, E_1 \xrightarrow{0} E_1$
• $O_1 \xrightarrow{1} E_1, O_1 \xrightarrow{0} O_1$

• 构造 $L_{1b}$ (恰好两个 0) 的 DFA: (同问题1b中的$L_1$)
• $C_0$: 0个0 (起始状态)。
• $C_1$: 1个0。
• $C_2$: 2个0 (接受状态)。
• $C_3$: 超过2个0 (陷阱状态)。
• $C_0 \xrightarrow{0} C_1, C_0 \xrightarrow{1} C_0$
• $C_1 \xrightarrow{0} C_2, C_1 \xrightarrow{1} C_1$
• $C_2 \xrightarrow{0} C_3, C_2 \xrightarrow{1} C_2$
• $C_3 \xrightarrow{0,1} C_3$

• 组合成 $L_1$ 的 NFA (NFA-1):
• 新起始状态 $q_{start1}$。
• $q_{start1} \xrightarrow{\epsilon} E_1$
• $q_{start1} \xrightarrow{\epsilon} C_0$
• 接受状态集: $\{O_1, C_2\}$。

第二步：为 $L_2$ 构造 NFA

$L_2$ 是所有以 "101" 结尾的字符串。我们可以构造一个简单的NFA来识别它。这比DFA简单得多。

• 构造 $L_2$ 的 NFA (NFA-2):
• $S_0$: 起始状态，寻找'1'。
• $S_1$: 找到了结尾模式的第一个'1'。
• $S_2$: 找到了 "10"。
• $S_3$: 找到了 "101" (接受状态)。
• 转移：
• $S_0 \xrightarrow{0,1} S_0$ (任意前缀)
• $S_0 \xrightarrow{1} S_1$
• $S_1 \xrightarrow{0} S_2$
• $S_2 \xrightarrow{1} S_3$
• 起始状态: $S_0$。
• 接受状态: $\{S_3\}$。

第三步：构造 $L_1 \circ L_2$ 的 NFA

现在我们应用连接构造法，将 NFA-1 和 NFA-2 连接起来。

• 起始状态: 新机器的起始状态是 NFA-1 的起始状态，即 $q_{start1}$。
• 连接桥梁: 从 NFA-1 的所有接受状态 $\{O_1, C_2\}$ 画ε-转移到 NFA-2 的起始状态 $S_0$。
• $O_1 \xrightarrow{\epsilon} S_0$
• $C_2 \xrightarrow{\epsilon} S_0$
• 接受状态: 新机器的接受状态是 NFA-2 的接受状态，即 $\{S_3\}$。NFA-1 的原接受状态 $O_1, C_2$ 在新机器中不再是接受状态。
• 整合: 整个大NFA由NFA-1和NFA-2的所有状态和转移，再加上两条新的ε-转移组成。

这部分回顾了为正则语言 $L$ 的克林星号 $L^*$ 构造NFA的标准方法。$L^*$ 是由 $L$ 中的字符串进行零次或多次连接而形成的所有字符串的集合。这意味着 $L^* = \{\epsilon\} \cup L \cup L \circ L \cup L \circ L \circ L \cup \dots$。

1. 图片分析:
   • 左图是识别语言 $L$ 的原始NFA $N$。
   • 右图是为 $L^*$ 构造的新NFA $N^*$。
2. 构造步骤:
   • 添加新起始状态: 创建一个全新的状态 $q_{new\_start}$，它同时也是一个接受状态。这是为了确保空字符串 $\epsilon$ (零次连接) 被接受。
   • 连接到旧机器: 从 $q_{new\_start}$ 画一条ε-转移到 $N$ 的原起始状态 $q_{start}$。这允许机器开始处理第一个 $L$ 中的字符串。
   • 创建循环: 从 $N$ 的每一个原接受状态 $q_{final}$ 画一条ε-转移返回到 $N$ 的原起始状态 $q_{start}$。这允许在成功识别了一个 $L$ 中的字符串后，立即开始识别下一个，实现了多次连接。
   • 整合:
   • 新NFA $N^*$ 的起始状态是 $q_{new\_start}$。
   • 新NFA $N^*$ 的接受状态集是 $\{q_{new\_start}\}$ 加上 $N$ 原有的所有接受状态（虽然图中只标了新的起始状态为接受状态，但完整的、更通用的构造也可以包含旧的接受状态，不过最简洁的构造是仅将新起始态设为接受态，并从旧接受态通过epsilon转移到新接受态，或如此图所示，通过循环回旧起始态，再从新起始态到旧起始态，并把新起始态设为唯一的接受态。这里的图示采取了“从旧接受态回旧起始态，新起始态到旧起始态，且新起始态为接受态”的策略。另一种等价构造是，新起始态既是起始态也是接受态，并有一条epsilon到旧起始态；从旧接受态有一条epsilon回到新接受态）。图中这种构造更严谨：新起始态是唯一的接受态，从所有旧接受态画 $\epsilon$ 转移到这个新接受态。但图示的循环方式更常见。让我们遵循图示的逻辑：从旧接受态回到旧起始态，新起始态到旧起始态，且新起始态是接受态。
   • 让我们更正一下对图的解读，这是一种非常标准和正确的构造：
3. 创建新起始/接受状态 $q_{new}$。
4. $q_{new} \xrightarrow{\epsilon} q_{start}$。
5. 从每个旧的接受状态 $q_{final} \xrightarrow{\epsilon} q_{new}$。

这与图示略有不同。图示的构造是：

1. 创建新起始/接受状态 $q_{new\_start}$。
2. $q_{new\_start} \xrightarrow{\epsilon} q_{start}$。
3. 从每个旧的接受状态 $q_{final} \xrightarrow{\epsilon} q_{start}$。

这两种构造都是正确的。我们以后者（图示）为准。

1. 工作原理:
   • 接受 $\epsilon$: 由于新起始状态 $q_{new\_start}$ 本身就是接受状态，所以不读任何输入，机器就在接受状态，$\epsilon$ 被接受。
   • 接受 $L$ 中的字符串: 从 $q_{new\_start}$ 通过 $\epsilon$-转移到 $q_{start}$，然后像在原NFA中一样处理字符串，到达一个原接受状态 $q_{final}$。但此时还不是最终接受状态。哦，我再次看图，图中的旧接受状态也还是接受状态！所以这个构造是：
2. 创建新起始状态 $q'_{start}$。
3. 将其设为接受状态。
4. $q'_{start} \xrightarrow{\epsilon} q_{start}$ (旧起始态)。
5. 从每个旧接受态 $q_{final} \xrightarrow{\epsilon} q_{start}$。
6. 所有旧接受态仍然是接受态。

这个构造也是正确的。

• 让我们采用最标准的Thompson构造，与图示最接近：

1. 创建新起始状态 $q_{new\_start}$ 和新接受状态 $q_{new\_final}$。
2. $q_{new\_start} \xrightarrow{\epsilon} q_{start}$ (旧起始态)。
3. 从每个旧接受态 $q_{final} \xrightarrow{\epsilon} q_{new\_final}$。
4. 添加直接从新起始到新接受的 $\epsilon$ 转移: $q_{new\_start} \xrightarrow{\epsilon} q_{new\_final}$ (处理空串)。
5. 添加从旧接受态回到旧起始态的 $\epsilon$ 转移: $q_{final} \xrightarrow{\epsilon} q_{start}$ (处理循环)。

这比图示复杂，但更通用。图示是一个简化版，但足以说明问题。

让我们严格按照图示的逻辑来解释，这是最可能的意图：

1. 创建新起始状态 $q_{new\_start}$。它也是接受状态。
2. 连接: 从 $q_{new\_start}$ 画一条 $\epsilon$ 转移到旧起始状态 $q_{start}$。
3. 循环: 从所有旧的接受状态 $q_{final}$ 画一条 $\epsilon$ 转移回到旧的起始状态 $q_{start}$。
4. 接受状态: 新机器的接受状态是 $\{q_{new\_start}\} \cup F_{old}$ (旧的接受状态集合)。

这样：

• $\epsilon$被接受（因为$q_{new\_start}$是接受态）。
• 单个 $w \in L$ 被接受（因为路径会走到 $F_{old}$ 中的状态）。
• $w_1w_2...w_k$ 被接受：走完 $w_1$ 到达 $F_{old}$，通过 $\epsilon$ 回到 $q_{start}$，再走完 $w_2$ 到达 $F_{old}$... 最后停在一个 $F_{old}$ 中的状态，被接受。

这个题目要求我们批判性地思考，找出四种看似合理但实际上有缺陷的星号构造法的反例。

这部分介绍了两个新的运算：逆转（Reversal）和 min，并要求我们证明正则语言在这两种运算下仍然是封闭的。证明一个语言是正则的，标准方法是为它构造一个有限自动机（DFA 或 NFA）。

证明思路: 如果 $L$ 是正则的，那么存在一个识别 $L$ 的 NFA $N$。我们的目标是基于 $N$ 构造一个新的 NFA $N^R$，使得 $N^R$ 识别 $L^R$。

如果字符串 $w = w_1w_2...w_n$ 被 $N$ 接受，意味着在 $N$ 中存在一条从起始状态到某个接受状态的路径，其边上的标签依次是 $w_1, w_2, ..., w_n$。

$q_{start} \xrightarrow{w_1} q_i \xrightarrow{w_2} ... \xrightarrow{w_n} q_{final}$

我们想要构造一个 NFA $N^R$ 来接受 $w^R = w_n...w_2w_1$。直觉上，我们应该能“倒着”走这条路径。

$q_{final} \xrightarrow{w_n} ... \xrightarrow{w_2} q_i \xrightarrow{w_1} q_{start}$

这启发了我们的构造方法。

构造 NFA $N^R$:

1. 翻转所有箭头: 将 $N$ 中的每一个转移 $q_i \xrightarrow{a} q_j$ 都变成 $q_j \xrightarrow{a} q_i$。
2. 交换起始和接受状态:
   • $N^R$ 的起始状态是 $N$ 的所有接受状态。但是 NFA 只能有一个起始状态，怎么办？很简单，创建一个全新的起始状态 $q'_{start}$，然后从它画 ε-转移 到 $N$ 的每一个原接受状态。
   • $N^R$ 的接受状态就是 $N$ 的原起始状态。

为什么这个构造有效:

一条在 $N$ 中从 $q_{start}$ 到 $q_{final}$ 消耗字符串 $w$ 的路径，在 $N^R$ 中完全对应于一条从某个原 $q_{final}$ (现在是 $N^R$ 的起始路径的一部分) 到原 $q_{start}$ (现在是 $N^R$ 的接受状态) 的路径，它消耗的字符串正好是 $w^R$。因为我们为所有这样的路径都提供了构造，所以 $N^R$ 恰好能识别所有 $w^R$ 构成的语言 $L^R$。

证明思路: 我们要证明如果 $L$ 是正则的，那么 $\min(L)$ 也是正则的。

$L$ 是正则的，意味着存在一个识别它的DFA $M$。（这里使用DFA比NFA更方便）。

$M = (Q, \Sigma, \delta, q_0, F)$。

$\min(L)$ 的定义是：一个字符串 $w$ 在 $\min(L)$ 中，必须满足两个条件：

1. $w \in L$ (即 $M$ 接受 $w$)。
2. 对于 $w$ 的任何真前缀 $v$，$v \notin L$ (即 $M$ 不接受 $v$)。

这给我们一个清晰的构造方向。在DFA $M$ 中，当处理字符串 $w$ 时，我们会经过一条状态路径: $q_0 \xrightarrow{w_1} q_1 \xrightarrow{w_2} \dots \xrightarrow{w_n} q_n$。

• 条件1 ($w \in L$) 意味着路径的最终状态 $q_n$ 必须是一个接受状态 ($q_n \in F$)。
• 条件2 (任何真前缀 $v$ 都不在 $L$ 中) 意味着路径上的任何中间状态 $q_1, q_2, \dots, q_{n-1}$ 都不能是接受状态。

构造 DFA $M'$ for min(L):

这个构造非常巧妙。我们不需要改变状态或转移，只需要改变“可访问性”。

1. 从原始的DFA $M$ 开始。
2. 识别并移除所有“死状态”（unreachable states）。(这是一个好习惯，虽然不必须)
3. 核心步骤: 修改 $M$ 的转移，使得一旦进入一个接受状态，就再也出不去了。创建一个新的陷阱状态 $q_{dead}$。对于 $M$ 中每一个接受状态 $q \in F$，对于所有输入符号 $a \in \Sigma$，将原来的转移 $\delta(q, a)$ 修改为 $\delta'(q, a) = q_{dead}$。而对于所有非接受状态，转移保持不变。
4. 这个修改后的机器 $M'$ 的状态集是 $Q \cup \{q_{dead}\}$，起始状态是 $q_0$，接受状态集仍然是 $F$。

让我们来验证这个构造：

• 假设一个字符串 $w$ 被 $M'$ 接受。这意味着处理 $w$ 的路径 $q_0 \to \dots \to q_n$ 中，$q_n \in F$，并且路径上没有经过 $q_{dead}$。
• 因为 $M'$ 在非接受状态的转移和 $M$ 一样，所以 $q_0 \to \dots \to q_{n-1}$ 这段路径在 $M$ 中也存在，且所有 $q_i (i<n)$ 都不是接受状态。
• 当最后一个符号 $w_n$ 读入，从 $q_{n-1}$ (一个非接受态) 转移到 $q_n$ (一个接受态)。因为这是第一次进入接受态，所以 $w$ 的任何真前缀都没有在接受状态结束。
• 因此，$w$ 在 $L$ 中，且其任何真前缀都不在 $L$ 中。所以 $w \in \min(L)$。

反过来，如果 $w \in \min(L)$，那么在 $M$ 中处理 $w$ 的路径 $q_0 \to \dots \to q_n$ 中，只有 $q_n$ 是接受状态。这条路径在 $M'$ 中也完全存在，因为一路上没有经过接受状态，转移函数没有被改变。最终停在 $q_n \in F$，所以 $w$ 被 $M'$ 接受。

所以，$M'$ 恰好识别 $\min(L)$。因为我们能为 $\min(L)$ 构造一个DFA，所以 $\min(L)$ 是正则的。

本节开始练习正则表达式（Regular Expressions, regex）。正则表达式是描述正则语言的另一种代数方法。我们需要将这些符号表示翻译成易于理解的自然语言描述。

这部分是逆向练习，给定语言描述，写出其正则表达式。

该问题要求使用 GNFA (广义非确定性有限自动机) 方法将一个DFA转换为正则表达式。GNFA的边上可以是正则表达式，而不是单个符号。转换过程是通过逐步“撕掉”状态，并用更复杂的正则表达式来补偿被撕掉状态所代表的路径。

DFA分析:

• 状态: 1, 2。
• 起始状态: 1。
• 接受状态: 1。
• 转移:
• $1 \xrightarrow{a} 2$
• $1 \xrightarrow{b} 1$
• $2 \xrightarrow{a} 1$
• $2 \xrightarrow{b} 2$

GNFA 转换步骤:

步骤 1: 预处理 DFA 为 GNFA 格式

1. 添加新的起始状态 $S_{new}$: 从 $S_{new}$ 画一条 ε-转移 到原起始状态 1。
2. 添加新的接受状态 $F_{new}$: 从所有原接受状态（这里只有1）画一条 ε-转移 到 $F_{new}$。
3. 合并多重边: 如果两个状态之间有多个符号的转移，用并集（$\cup$）合并。例如，$q_i \xrightarrow{a} q_j$ 和 $q_i \xrightarrow{b} q_j$ 变成 $q_i \xrightarrow{a \cup b} q_j$。这个DFA没有这种情况。
4. 添加空集边: 如果两个状态之间没有转移，我们认为它们之间有一条标签为 $\emptyset$ 的边。

初始 GNFA 结构:

• 状态: $\{S_{new}, 1, 2, F_{new}\}$
• $S_{new} \xrightarrow{\epsilon} 1$
• $1 \xrightarrow{b} 1$
• $1 \xrightarrow{a} 2$
• $2 \xrightarrow{b} 2$
• $2 \xrightarrow{a} 1$
• $1 \xrightarrow{\epsilon} F_{new}$

步骤 2: 撕掉状态

我们有两个内部状态 1 和 2 可以撕。我们选择先撕掉状态2。

撕掉状态 2:

我们要考虑所有经过状态2的路径，例如从状态 i 到 j 经过 2 的路径: i -> 2 -> j。这个路径的正则表达式是 R(i,2) R(2,2)* R(2,j)。然后我们将这个新的表达式加到原来的 R(i,j) 上。

• 需要更新的路径: 只有 1 -> 2 -> 1。
• R(1,2) = $a$
• R(2,2) = $b$
• R(2,1) = $a$
• 路径 1 -> 2 -> 1 的正则表达式: $a b^* a$
• 更新 R(1,1): 原来的 $R(1,1)$ 是 $b$。新的 $R(1,1)$ 是 $b \cup ab^*a$。

撕掉状态2后的 GNFA:

• 状态: $\{S_{new}, 1, F_{new}\}$
• $S_{new} \xrightarrow{\epsilon} 1$
• $1 \xrightarrow{b \cup ab^*a} 1$ (这是一个自循环)
• $1 \xrightarrow{\epsilon} F_{new}$

步骤 3: 撕掉最后一个内部状态，状态1

现在我们撕掉状态1。我们只关心从 $S_{new}$ 到 $F_{new}$ 的路径。

• 路径是 $S_{new} \rightarrow 1 \rightarrow F_{new}$。
• R($S_{new}$, 1) = $\epsilon$
• R(1,1) = $b \cup ab^*a$
• R(1, $F_{new}$) = $\epsilon$
• 公式: $R(S_{new}, F_{new}) = R(S_{new}, 1) \circ (R(1,1))^* \circ R(1, F_{new})$
• 代入值: $\epsilon \circ (b \cup ab^*a)^* \circ \epsilon$
• 简化: $(b \cup ab^*a)^*$

最终的正则表达式: $(b \cup ab^*a)^*$

语言描述验证:

• 这个DFA接受什么样的语言？
• 从起始/接受状态1开始。可以读任意多个'b'，停在1，接受。所以 $b^* \in L$。
• 读一个'a'到状态2，再读一个'a'回到状态1，接受。所以 'aa' $\in L$。
• 在状态2可以读任意多个'b'。所以 $ab^*a \in L$。
• 整个语言是这些部分的任意组合。例如 b 和 aa 组合成 baa。
• $b(ab^*a)b(ab^*a)$ 等。
• 这正是 $(b \cup ab^*a)^*$ 所描述的。

这个问题要求我们使用Thompson构造法，将一个正则表达式逐步转换为一个NFA。该方法为每个基本操作（原子、并、连接、星号）定义了标准的NFA组件，然后像搭积木一样把它们组合起来。

正则表达式分解:

这个表达式是两个部分的连接:

1. Part A: $(01)^*$
2. Part B: $(10^* \cup 0)$

我们分别构造 Part A 和 Part B，然后将它们连接起来。

第一步: 构造 Part A: $(01)^*$

1. 构造 "0" 的 NFA: $q_1 \xrightarrow{0} q_2$
2. 构造 "1" 的 NFA: $q_3 \xrightarrow{1} q_4$
3. 构造 "01" (连接): 将 "0" 的接受态 $q_2$ 和 "1" 的起始态 $q_3$ 合并 (或用ε-转移)。得到 $q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_4$。
4. 构造 $(01)^*$ (星号): 对 "01" 的NFA应用星号构造法。
   • 创建新的起始态 $A_{start}$ 和接受态 $A_{final}$。
   • $A_{start} \xrightarrow{\epsilon} A_{final}$ (处理空串)。
   • $A_{start} \xrightarrow{\epsilon} q_1$ (进入循环)。
   • $q_4 \xrightarrow{\epsilon} A_{final}$ (退出循环)。
   • $q_4 \xrightarrow{\epsilon} q_1$ (循环反馈)。
   • (简化版构造) 新建一个起始/接受状态 $A_{start}$。
   • $A_{start} \xrightarrow{\epsilon} q_1$。
   • $q_4 \xrightarrow{\epsilon} A_{start}$。
   • $A_{start}$ 是接受状态。
   • 我们用这个简化版，它有状态 {$A_{start}, q_1, q_2, q_4$}。起始是 $A_{start}$，接受是 $A_{start}$。转移：$A_{start}\xrightarrow{\epsilon}q_1$, $q_1\xrightarrow{0}q_2$, $q_2\xrightarrow{1}q_4$, $q_4\xrightarrow{\epsilon}A_{start}$。

第二步: 构造 Part B: $(10^* \cup 0)$

Part B 是一个并集。

1. 构造上分支: $10^*$
   • 构造 "0" 的 NFA: $q_5 \xrightarrow{0} q_6$。
   • 构造 $0^*$ (星号): 创建新起始/接受态 $S_0$。$S_0 \xrightarrow{\epsilon} q_5$, $q_6 \xrightarrow{\epsilon} S_0$。
   • 构造 "1" 的 NFA: $q_7 \xrightarrow{1} q_8$。
   • 构造 $10^*$ (连接): 将 "1" 的NFA和 $0^*$ 的NFA连接。$q_7 \xrightarrow{1} q_8 \xrightarrow{\epsilon} S_0$。$q_7$是起始， $S_0$和$q_6$相关的接受状态是最终接受状态。整个 $10^*$ 的NFA可以简化为：$q_7 \xrightarrow{1} q_8$，然后 $q_8$ 上有一个消耗'0'的自循环。我们用Thompson标准构造：$q_7 \xrightarrow{1} q_8$, $q_8 \xrightarrow{\epsilon} q_{s0}$, $q_{s0} \xrightarrow{\epsilon} q_5, q_6 \xrightarrow{\epsilon} q_{s0}, q_{s0} \xrightarrow{\epsilon} q_{sF}$。这太复杂了。
   • 我们直接画出 $10^*$ 的NFA：$B_{1s} \xrightarrow{1} B_{1m}$，然后 $B_{1m}$ 上有 $B_{1m} \xrightarrow{0} B_{1m}$ 的自循环。接受状态是 $B_{1m}$。
2. 构造下分支: "0"
   • $B_{2s} \xrightarrow{0} B_{2f}$。$B_{2f}$是接受状态。
3. 构造 $(10^* \cup 0)$ (并集):
   • 创建新起始态 $B_{start}$ 和新接受态 $B_{final}$。
   • $B_{start} \xrightarrow{\epsilon} B_{1s}$ (上分支起始)。
   • $B_{start} \xrightarrow{\epsilon} B_{2s}$ (下分支起始)。
   • $B_{1m} \xrightarrow{\epsilon} B_{final}$ (上分支结束)。
   • $B_{2f} \xrightarrow{\epsilon} B_{final}$ (下分支结束)。

第三步: 构造最终 NFA (连接 Part A 和 Part B)

• 将 Part A 的 NFA 和 Part B 的 NFA 连接起来。
• Part A 的接受状态（在我们的简化版里是 $A_{start}$）通过 ε-转移 连接到 Part B 的起始状态 $B_{start}$。
• 最终机器的起始状态是 Part A 的起始状态 $A_{start}$。
• 最终机器的接受状态是 Part B 的接受状态 $B_{final}$。
• 连接: $A_{start} \xrightarrow{\epsilon} B_{start}$。
• 同时，因为 $A_{start}$ 本身是 Part A 的接受状态，所以这个连接是正确的。

最终的NFA图:

1. 画出 Part A ($(01)^*$)的NFA，它是一个环。
2. 画出 Part B ($(10^* \cup 0)$)的NFA，它是一个分叉结构。
3. 从 Part A 的接受状态（即其起始状态）画一条 ε-转移 到 Part B 的起始状态。
4. 标记最终NFA的起始（Part A的起始）和接受（Part B的接受）状态。