来自 vczh

?

1：字符集

??

字符集是正则表达式最基本的元素，因此反映到状态图上，字符集也会是构成状态图的基本元素。对于字符集C，如果有一个规则只接受C的话，这个规则对应的状态图将会被构造成以下形式：

??

??

这个状态图的初始状态是Start，结束状态是End。Start状态读入字符集C跳转到End状态，不接受其他字符集。

??

2：串联

??

如果我们使用A⊙B表示规则A和规则B的串联，我们可以很容易的知道串联这个操作具有结合性，也就是说(A⊙B)⊙C=A⊙(B⊙C)。因此对于n个规则的串联，我们只需要先将前n-1个规则进行串连，然后把得到的规则看成一个整体，跟最后一个规则进行串联，那么就得到了所有规则的串联。如果我们知道如何将两个规则串联起来的话，也就等于知道了如何把n个规则进行串联。

??

为了将两个串联的规则转换成一个状态图，我们只需要先将这两个规则转换成状态图，然后让第一个状态的结束状态跳转到第二个状态图的起始状态。这种跳转必须是不读入字符的跳转，也就是令这两个状态等价。因此，第一个状态图跳转到了结束状态的时候，就可以当成第二个状态图的起始状态，继续第二个规则的检查。因此我们使用了ε边连接两个状态图：

??

3：并联

??

并联的方法跟串联类似。为了可以在起始状态读入一个字符的时候就知道这个字符可能走的是并联的哪一些分支并进行跳转，我们需要先把所有分支的状态图构造出来，然后把起始状态连接到所有分支的起始状态上。而且，在某个分支成功接受了一段字符串之后，为了让那个状态图的结束状态反映在整个状态图的结束状态上，我们也把所有分支的结束状态都连接到大规则的结束状态上。如下所示：

??

4：重复

??

对于一个重复，我们可以设立两个状态。第一个状态是起始状态，第二个状态是结束状态。当状态走到结束状态的时候，如果遇到一个可以让规则接受的字符串，则再次回到结束状态。这样的话就可以用一个状态图来表示重复了。于是对于重复，我们可以构造状态图如下所示：

??

5：可选

??

为可选操作建立状态图比较简单。为了完成可选操作，我们需要在接受一个字符的时候，如果字符串的前缀被当前规则接受则走当前规则的状态图，如果可选规则的后续规则接受了字符串则走后续规则的状态图，如果都接受的话就两个图都要走。为了达到这个目的，我们把规则的状态图的起始状态和结束状态连接起来，得到了如下状态图：

??

??

如果重复使用的是0次以上重复，也就是原来的重复加上可选的结果，那么可以简单地把图4.4的Start状态去掉，让End状态同时拥有起始状态和结束状态两个角色，[Start]和[End]则保持原状。

??

至此，我们已经将5种构造状态图的办法都对应到了5种构造规则的办法上了。对于任意的一个正则表达式，我们仅需要把这个表达式还原成那5种构造的嵌套，然后把每一步构造都对应到一个状态图的构造上，就可以将一个正则表达式转换成一个ε-NFA了。

??

??