五、消除非确定性
消除ε边算法
我们见到的有穷状态自动机一共有三种：ε-NFA、NFA和DFA。现在我们需要将ε-NFA转换为DFA。一个DFA中不可能出现ε边，所以我们首先要消除ε边。消除ε边算法基于一个很简单的想法：如果状态A通过ε边到达状态B的话，那么状态A无需读入字符就可以直达状态B。如果状态B需要读入字符x才可以到达状态C的话，那么状态A读入x也可以到达状态C。因为从A到C的路径是A B C，其中A到B不需要读入字符。
于是我们会得到一个很自然的想法：消除从状态A出发的ε边，只需要寻找所有从A开始仅通过ε边就可以到达的状态，并把从这些状态触出发的非ε边复制到A上即可。剩下的工作就是删除所有的ε边和一些因为消除ε边而变得不可到达的状态。为了更加形象地描述消除ε边算法，我们从正则表达式(ab|cd)*构造一个ε-NFA，并在此状态机上应用消除ε边算法。
正则表达式(ab|cd)*的状态图如下所示：
图5.1
1：找到所有有效状态。
有效状态就是在完成了消除ε边算法之后仍然存在的状态。我们可以在开始整个算法之前就预先计算出所有有效状态。有效状态的特点是存在非ε边的输入。同时，起始状态也是一个有效状态。结束状态不一定是有效状态，但是如果存在一个有效状态可以仅通过ε边到达结束状态的话，那么这个状态应该被标记为结束状态。因此对一个ε-NFA应用消除ε边算法产生的NFA可能出现多个结束状态。不过起始状态仍然只有一个。
我们可以把“存在非ε边的输入或者起始状态”这个判断方法应用在图5.1每一个状态上，计算出图5.1中所有的有效状态。结果如下图所示。
图5.2
所有非有效状态的标签都被删除
如果一个状态同时具有ε边和非ε边输入的话，那么这个状态仍然是有效状态。因为所有的有效状态在下一步的操作中，都会得到新的输出和新的输入。
2：添加所有必要的边
接下来我们要对所有的有效状态都应用一个算法。这个算法分成两步。第一步是寻找一个状态的ε闭包，第二步是把这个状态的ε闭包看成一个整体，把所有从这个闭包中输出的边全部复制到当前状态上。从标记有效状态的结果我们得到了图5.1状态图的有效状态集合是{S/E 3 5 7 9}。我们依次对这些状态应用上述算法。第一步，计算S/E状态的ε闭包。所谓一个状态的ε闭包就是从这个状态出发，仅通过ε边就可以到达的所有状态的集合。下图中标记出了状态S/E的ε闭包：
图5.3
现在，我们把状态S/E从状态S/E的ε闭包中排除出去。因为从状态A输出的非ε边都属于从状态A的ε闭包中输出的非ε边，复制这些边是没有任何价值的。接下来就是找到从状态S/E的ε闭包中输出的非ε边。在图5.3我们可以很容易地发现，从状态1和状态6(见图5.1的状态标签)分别输出到状态3和状态7的标记了a或者b的边，就是我们所要寻找的边。接下来我们把这些边复制到状态S/E上，边的目标状态仍然保持不变，可以得到下图：
图5.4
至此，这个算法在S/E上的应用就结束了，接下来我们分别对剩下的有效状态{3 5 7 9}分别应用此算法，可以得到下图：
图5.5
红色的边为新增加的边
3：删除所有ε边和无效状态
这一步操作是消除ε边算法的最后步骤。我们只需要删除所有的ε边和无效状态就完成了整个消除ε边算法。现在我们对图5.5的状态机应用第三步，得到如下状态图：
图5.6
不过并不是只有新增的边才不被删除。根据定义，所有从有效状态出发的非ε边都是不能删除的边。
我们通过把消除ε边算法应用在图5.1的状态机上，得到了图5.6这个DFA。但是并不是所有的消除ε边算法都可以直接从ε-NFA直接得到DFA，这个其实跟正则表达式本身有关。至于什么正则表达式可以达到这个效果这里就不深究了。但是因为有可能产生NFA，所以我们还需要一个算法把NFA转换成DFA。