如何从NFA转换到DFA
在上一篇文章里面，Shellex阐述了将正则表达式转换成NFA的通用方法，算是对以前编译原理课程的回炉重炼了一遍。
下面Shellex将重炼进行下去。对于一个NFA，如何转换成DFA呢？
根据上回说的，一个 NFA 在读入符号串之后，并不确切地知道自动机的下一个状态是什么。但可以肯定的是，下一个状态一定处于某个状态集中。不妨该状态集记做 {q1,q2,…qk} 。
而一个等价的DFA 读入同样的符号串一定处于某个确定的状态上。
这样，都是读入同样的w， DFA 到达某一个状态，而 NFA 到达某一个状态集。由 w 的任意性，可将 NFA 的所有的状态集和 DFA 的状态一一对应起来。这种对应的前提就是能识别同样的输入串。即 L(M1)=L(M2) 。
所以可以看出，我们要做的就是将 NFA 状态集归并为 DFA 中的状态。
为了归并的成功，Shellex先介绍三种基本操作：
ε-closure(s)：从状态s出发，返回仅仅通过ε边可以到达的最大状态集合
ε-closure(T)：从状态集合T中的每一个状态出发，返回仅仅通过ε边可以到达的最大状态集合
move(T, w)：从状态集合T中的每一状态出发，返回w边指向的下一个状态的集合
接下来Shellex用一个NFA为例，分析整个过程：
可以看到，这是一个典型的NFA。状态1到状态2存在ε边，而状态3有两个b边，分别指向自己和状态4。
S1=ε-closure(1); //S1={1,2}
S1a = move(S1, 'a'); //S1a = {3}
S1b = move(S1, 'b'); //S1b = {}
S2 = ε-closure(S1a); //S2 = {3}
S2a = move(S2, 'a'); //S2a={}
S2b = move(S2, 'b'); //S2b={3, 4}
S3 = ε-closure(S2b); //S3={3, 4}
S3a = move(S3, 'a'); //S3a={}
S3a = move(S3, 'b'); //S3a={3}
现在，根据上面的过程，NFA所有状态集合己都已经生成：S1={1, 2}， S2={3}，S3={3,4}，那 么让这些状态集合接管它们的元素的所有转换边关系，得到:
S2 = ε-closure(S1a); //S2 = {3}
S3 = ε-closure(S2b); //S3={3, 4}
这两步怎么来的，为什么选S1a和S2b。
S2b = move(S2, ‘b’); //S2b={3, 4}
这里都搞错了吧