学步园

在上一篇文章中，已经得到了与正则表达式等价的 NFA，本篇文章会说明如何从 NFA 转换为 DFA，以及对 DFA 和字符类进行化简。
一、DFA 的表示

DFA 的表示与 NFA 比较类似，不过要简单的多，只需要一个添加新状态的方法即可。Dfa 类的代码如下所示：

DFA 的状态也比较简单，必要的属性只有两个：符号索引和状态转移。

符号索引表示当前的接受状态对应的是哪个正则表达式。不过 DFA 的一个状态可能对应于 NFA 的多个状态（详见下面的子集构造法），所以 DFA 状态的符号索引是一个数组。对于普通状态，符号索引是空数组。

状态转移表示如何从当前状态转移到下一状态，由于在构造 NFA 时已经划分好了字符类，所以在 DFA 中直接使用数组记录下不同字符类对应的转移（DFA 中是不存在 ϵ 转移的，而且对每个字符类有且只有一条转移）。

在 NFA 的状态定义中，还有一个状态类型属性，但是在 DFA 状态中却没有这个属性，是因为 Trailing 类型的状态会在 DFA 匹配字符串的时候处理（会在下篇文章中说明），TrailingHead 类型的状态会在构造 DFA 的时候与 Normal 类型的状态合并（详见 2.4 节）。

下面是 DfaState 类的定义：

DFA 的状态中额外定义的两个属性 Dfa 和 Index 同样是为了方便状态的使用。
二、NFA 转换为 DFA
2.1 子集构造法

将 NFA 转换为 DFA，采用的是子集构造（subset construction）算法。该算法的过程与《C# 词法分析器（三）正则表达式》的 3.1 节中提到的 NFA 匹配过程比较相似。在 NFA 的匹配过程中，使用的都是 NFA 的一个状态集合，那么子集构造法就是用 DFA 的一个状态来对应 NFA 的一个状态集合，即 DFA 读入输入字符串 a1a2⋯an 之后到达的状态，就对应于 NFA 读入同样的字符串 a1a2⋯an 之后到达的状态的集合。

子集构造算法需要用到的操作有：

我们需要找到的是当一个 NFA N 读入了某个输入串后，可能位于的所有状态集合。

首先，在读入第一个字符之前，N 可以位于 ϵ-closure(s0) 中的任何状态，其中 s0 是 N 的开始状态。那么，此时 ϵ-closure(s0) 就表示 DFA 的开始状态。

假设 N 在读入输入串 x 之后可以位于集合 T 中的状态上，下一个输入字符是 a，那么 N 可以立即移动到 move(T,a) 中的任何状态，并且还可以通过 ϵ 转移来移动到 ϵ-closure(move(T,a)) 中的任何状态上。这样的每个不同的 ϵ-closure(move(T,a)) 就表示了一个 DFA 的状态。如果这个说明难以理解，可以参考后面给出的示例。

据此，可以得到以下的算法（算法中的 T[a]=U 表示在状态 T 中的字符类 a 上存在到状态 U 的转移）：

输入：一个 NFA N
输出：与 NFA 等价的 DFA D
一开始，ϵ-closure(s0) 是 D 中的唯一状态，且未被标记
while (在 D 中存在未被标记的状态 T) {
 为 T 加上标记
 foreach (每个字符类 a) {
U=ϵ-closure(move(T,a))
  if (U 不在 D 中) {
   将 U 加入 D 中，且未被标记
  }
T[a]=U
 }
}

如果某个 NFA 是终结状态，那么所有包含它的 DFA 状态也是终结状态，而且 DFA 状态的符号索引就包含 NFA 状态对应的符号索引。一个 DFA 状态可能对应于多个 NFA 状态，所以上面定义 DfaState 时，符号索引是一个数组。

计算 ϵ-closure(T) 的过程就是从一个状态集合开始的简单图搜索过程，使用 DFS 即可实现，具体的算法如下（ϵ-closure(s) 的算法也同理，等价于 \epsilon \text{-} closure(\{s\})）：

输入：NFA 的状态集合 T
输出：\epsilon \text{-} closure(T)
将 T 的所有状态压入堆栈
\epsilon \text{-} closure(T) = T
while (堆栈非空) {
 弹出栈顶元素 t
 foreach (u : t 可以通过 \epsilon 转移到达 u) {
  if (u \notin \epsilon \text{-} closure(T)) {
\epsilon \text{-} closure(T) = \epsilon \text{-} closure(T) \cup \left\{ u \right\}
   将 u 压入堆栈
  }
 }
}

计算 move(T,a) 的算法更加简单，只有一个循环：

输入：NFA 的状态集合 T
输出：move(T,a)
move(T,a) = \emptyset
foreach (u \in T) {
 if (u 存在字符类 a 上的转移，目标为 t) {
move(T,a) = move(T,a) \cup \left\{ t \right\}
 }
}
2.2 子集构造法的示例
这里以上一节中从正则表达式 (a|b)*baa 构造得到的 NFA 作为示例，将它转化为 DFA。这里的输入字母表 \Sigma = \{a, b\}。

图 1 正则表达式 (a|b)*baa 的 NFA