五、消除非确定性

消除ε边算法

我们见到的有穷状态自动机一共有三种:ε-NFANFADFA。现在我们需要将ε-NFA转换为DFA。一个DFA中不可能出现ε边,所以我们首先要消除ε边。消除ε边算法基于一个很简单的想法:如果状态A通过ε边到达状态B的话,那么状态A无需读入字符就可以直达状态B。如果状态B需要读入字符x才可以到达状态C的话,那么状态A读入x也可以到达状态C。因为从AC的路径是A B C,其中AB不需要读入字符。

于是我们会得到一个很自然的想法:消除从状态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