NFA转DFA的子集构造(subset construction)算法

之前学习编译原理的时候老师有讲过子集构造法，当时我以为自己听懂了，信心满满。可是这两天我做了一些题目，发现自己实际上还是太嫩了，学习浮于表面。之后又重新看了龙书和虎书，对子集构造法有了更深层次的了解。特此发出一篇文章分享我的经验。

1 概念

概念是我们学习编译原理的重中之重，虽然他很晦涩难懂，但我有必要将其放在最开始。

1.1 虎书概念

虎书的概念更偏向于理论化，我当时看的时候一头雾水，但是不要担心，之后会一点一点解释的。

首先，我们形式化定义 $\epsilon$ 闭包如下：

$edge(s,c)$ ：状态 $s$ 沿着标有 $c$ 的边可到达的所有NFA状态的集合；
：对于状态集合，从出发，只通过边可以达到的状态集合；
- 这种经过 $\epsilon$ 边的概念可以用数学方法表述，即 $closure(S)$ 是满足如下条件的最小集合 $T$ ：
  $T=S \cup \left( \bigcup_{s \in T}edge(s,\epsilon) \right)$
- 我们可以用迭代法来算出 $T$ ：
  $T \leftarrow S \\ repeat \ T' \leftarrow T \\ \qquad \quad T \leftarrow T' \cup \left( \bigcup_{s \in T'}edge(s,\epsilon) \right) \\ until \ T=T'$

解释一下：当我们位于一个状态集合 $S$ ， $S$ 里任意状态经过若干 $\epsilon$ 能够到达的状态，都将包含在 $closure(S)$ 里。

龙书里将这个操作定义为 $\epsilon-closure(T)$ ( $T$ 为状态集合)。

现在，假设我们位于由NFA状态 $s_i,s_k,s_l$ 组成的集合 $d= \lbrace s_i,s_k,s_l \rbrace$ 中。从 $d$ 中的状态出发，输入符号 $c$ ，将到达NFA新的状态集；我们称这个状态集为 $DFAedge(d,c)$ ：

$DFAedge(d,c)=closure \left( \bigcup_{s \in d}edge(s,c) \right)$

解释一下：将遍历集合 $d$ 中的所有状态，得到 $d$ 关于 $T=edge(s,c)$ 的状态集，并对 $T$ 求 $closure(T)$ ，得到的即为 $DFAedge(d,c)$ 。简而言之，就是从一个状态集，经过一个输入到达的状态集为 $T'=DFAedge(d,c)$ 。

利用 $DFAedge$ 能更形式化地写出NFA模拟算法。如果初态是 $s_1$ ，输入字符串是 $c_1,...,c_k$ ，则算法为：

$d \leftarrow closure( \lbrace s_1 \rbrace ) \\ for \ i \leftarrow 1 \ to \ k \\ \quad d \leftarrow DFAedge(d,c_i)$

有了 $closure$ 和 $DFAedge$ 算法，就能构造出DFA，DFA的状态 $d_1$ 就是 $closure(s_1)$ 。抽象而言，如果 $d_j=DFAedge(d_i,c)$ 则存在一条从 $d_i$ 到 $d_j$ 的标记为 $c$ 的边。令 $\Sigma$ 是字母表：
$states[0] \leftarrow \lbrace \rbrace; \qquad states[1] \leftarrow closure(\lbrace s_1 \rbrace)\\ p\leftarrow 1; \qquad j \leftarrow 0 \\ while \ j \leq p \\ \ \ \ foreach \ c \in \Sigma \\ \qquad e \leftarrow DFAedge(states[j],c) \\ \qquad if \ e =states[i] \ for \ some \ i \leq p \\ \qquad \quad \ then \ trans[j,c] \leftarrow i \\ \qquad \quad \ else \ p \leftarrow p+1 \\ \qquad \qquad \quad \, states[p] \leftarrow e \\ \qquad \qquad \quad \, trans[j,c] \leftarrow p \\ \; \; j \leftarrow j+1$

解释一下： $state[]$ 代表了最终DFA的一个状态所对应的NFA状态集， $s_1$ 为初始状态， $closure(\lbrace s_1 \rbrace)$ 代表了初始状态 $s_1$ 的闭包。上文中的代码实际上和龙书的代码一个意思，龙书的代码更加简单直白，所以这里可以跳过。等看完下面的龙书再回头来看

1.2 龙书概念

个人认为龙书的概念更加通俗易懂，但是由于没有数学公式的归纳，导致理论基础不扎实，有点慌。所以推荐两本书一起看。

首先，是概念：

子集构造法的基本思想是让构造得到的DFA的每个状态对应NFA的一个状态集合。DFA在读入 $a_1a_2...a_n$ 之后到达的状态应该对应于相应的NFA从开始状态出发，沿着以 $a_1a_2...a_n$ 为边的路径能达到的状态的集合。

解释一下：概念很直观哈，我就不解释了^_^

接着，是算法：

输入：一个NFA N
输出：一个接受同样语言的DFA D
方法：我们为算法 D 构造一个转换表 $Dtran$ 。D的每个状态是一个NFA集合，构造 $Dtran$ ，使得 D “并行地”模拟 N 在遇到一个给定输入串可能执行的所有动作。下面我们给出一些函数的定义：

操作	描述
$\epsilon - closure(s)$	能够从NFA状态 $s$ 开始只通过 $\epsilon$ 转换到达的NFA状态集合
$\epsilon - closure(T)$	能够从 $T$ 中某个NFA状态 $s$ 开始只通过 $\epsilon$ 转换到达的NFA状态集合，即 $\bigcup_{s \in T} \epsilon -closure(s)$
$move(T,a)$	能够从 $T$ 中某个状态 $s$ 出发通过标号为 $a$ 的转换到达的NFA状态的集合

在读入第一个符号之前，N可以位于集合 $\epsilon-closure(s_0)$ 中的任何状态上，其中， $s_0$ 是 N 的开始状态。
下面进行回归纳：假定N在读入输入串之后可以位于集合T的任意状态上。如果下一个输入符号是，那么N可以立即移动到集合中的任何状态。然而，N 可以读入之后再执行几个转换，因此 N 在读入之后可以位于中的任意状态上。接着我们可以构造出转换函数 $Dtran$ ：
- 一开始， $\epsilon-clusure(s_0)$ 是 $Dstates$ 的唯一状态，且它未标记(请注意，“标记”是非常重要的概念)；
- $while(在\ Dstates\ 中有一个未标记的状态\ T) \lbrace \\ \quad \quad \ 给T加上标记; \\ \quad \quad \ for(每个输入符号a) \lbrace \\ \qquad \qquad \quad U=\epsilon-clusure\left(move(T,a) \right) \\ \qquad \qquad \quad if(U不在Dstates中) \\ \qquad \qquad \qquad \qquad \, 将U加入Dstates中，且不加标记; \\ \qquad \qquad \quad Dtran[T,a]=U \\ \quad \quad \ \rbrace \\ \rbrace$

解释一下：这部分代码和虎书上的代码意思相近，这个更好理解。算法里的 $Dtran[T,a]=\epsilon-clusure\left(move(T,a) \right)$ 每个 $Dtran[T,a]$ 都可能是DFA的一个状态。

2 举个例子解释

题目：给定一个正则表达式 $(a|b)^*abb$ 的NFA，我们使用子集构造法构造DFA。

NFA
解法：首先，我们分析得出，NFA的初始为状态0。因而初始状态集。
1. $A$ 被加上标记，对于输入符号 $a,b$ ，分别求出:
  $a:B=\epsilon-closure(move(A,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:C=\epsilon-closure(move(A,b))=\lbrace1,2,4,5,6,7 \rbrace$
2. $B,C$ 都没有被标记，因而将 $B,C$ 依次加上标记，对于输入符号 $a,b$ ，分别求出:
  $a:B=\epsilon-closure(move(B,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:D=\epsilon-closure(move(B,b))=\lbrace1,2,4,5,6,7,9 \rbrace$
  $a:B=\epsilon-closure(move(C,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:C=\epsilon-closure(move(C,b))=\lbrace1,2,4,5,6,7 \rbrace$
3. 现在只剩 $D$ 没有加标记，因而给 $D$ 加上标记，对于输入符号 $a,b$ ，分别求出:
  $a:B=\epsilon-closure(move(D,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:E=\epsilon-closure(move(D,b))=\lbrace1,2,4,5,6,7,10 \rbrace$
4. 还剩一个 $E$ 没有标记，因而给 $E$ 加上标记，对于输入符号 $a,b$ ，分别求出:
  $a:B=\epsilon-closure(move(E,a))=\lbrace1,2,3,4,6,7,8 \rbrace \\b:C=\epsilon-closure(move(E,b))=\lbrace1,2,4,5,6,7 \rbrace$
5. 所有构造出来的集合都已经被标记，构造完成！ $A,B,C,D,E$ 为五个不同状态：
  $A=\lbrace0,1,2,4,7 \rbrace \\ B=\lbrace1,2,3,4,6,7,8 \rbrace \\ C=\lbrace1,2,4,5,6,7 \rbrace \\ D=\lbrace1,2,4,5,6,7,9 \rbrace \\ E=\lbrace1,2,4,5,6,7,10 \rbrace$
6. 接着就是根据状态来画图了，最好先画好状态表：
  
  子集构造状态表

解释一下：由此可知， $A$ 通过 $a$ ，连到 $B$ ，以此类推。就可以做出DFA图了^_^

转换后的DFA状态图

3 如何最小化DFA的状态数量

很简单，如果开始于 $s_1$ 的机器接收字符串 $\sigma$ ，始于 $s_2$ 的和始于与 $s_1$ 接收的串相同，并到达相同状态，且两个状态集同为终态或者非终态，那么 $s_1,s_2$ 是等价的。我们可以把指向 $s_2$ 的连线全部指向 $s_1$ ，并删除 $s_2$ ，反之亦然。

举个书上的例子：

书上的NFA转DFA示例图
图中的 $\lbrace 5,6,8,15 \rbrace,\lbrace 6,7,8 \rbrace$ 是等价的，还有 $\lbrace 10,11,13,15 \rbrace,\lbrace 11,12,13 \rbrace$ 也是等价的。

Tips：在判断是否等价前，我们要先判断是否为死状态哦(1.不能到达终态 2.从开始没有路径指向这个状态)。

4 总结

NFA转DFA知识总结就到这里，有什么问题请留言，有错误请批评指正，非常感谢您的阅读。