图4.4
5 ：可选
为可选操作建立状态图比较简单。为了完成可选操作，我们需要在接受一个字符的时 候，如果字符串的前缀被当前规则接受则走当前规则的状态图，如果可选规则的后续规则接受了字符串则走后续规则的状态图，如果都接受的话就两个图都要走。为 了达到这个目的，我们把规则的状态图的起始状态和结束状态连接起来，得到了如下状态图：
图4.5
如果重复使用的是0次以上重复，也就是原来的重复加上可选的结果，那么可以简单地把图4.4的Start状态去掉，让End状态同时拥有起始状态和结束状态两个角色，[Start]和[End]则保持原状。
至此，我们已经将5种构造状态图的办法都对应到了5种构造规则的办法上了。对于 任意的一个正则表达式，我们仅需要把这个表达式还原成那5种构造的嵌套，然后把每一步构造都对应到一个状态图的构造上，就可以将一个正则表达式转换成一个 ε-NFA了。举个例子，我们使用正则表达式来表达“一个字符串仅包含偶数个a和偶数个b”，然后把它转换成ε-NFA。
我们先对这个问题进行分析。如果一个字符串仅包含偶数个a和偶数个b的话，那么 这个字符串一定是偶数长度的。于是我们可以把这个字符串分割成两个两个的字符段。而且这些字符段只有四种：aa、bb、ab和ba。对于aa和bb来说， 无论出现多少次都不会影响字符串中a和b的数量的奇偶性(理由：在一个模2加法系统里，0是不变项，也就是说对于任何属于模2加法的数X有X+0 = 0+X = X)。对于ab和ba的话，如果一个字符串的开始和结束是ab或者ba，中间的部分是aa或者bb的任意组合，这个字符串也是具有偶数个a和偶数个b的。 我们现在得到了两种构造偶数个a和偶数个b的字符串的方法。把串联、并联、可选、重复等操作应用在这些字符串上，仍然会得到具有偶数个a和偶数个b的字符 串。于是我们可以把正则表达式书写成以下形式：
((aa|bb)|((ab|ba)(aa|bb)*(ab|ba)))*
根据上文提到的方法，我们可以把这个正则表达式转换成以下状态机：
图4.6
至此，我们已经得到了把一个正则表达式转换为ε-NFA的方法了。但是只得到ε-NFA还是不行的，因为ε-NFA的不确定性太大了，直接根据ε-NFA跑的话，每一次都会得到大量的临时状态集合，会极大地降低效率。因此，我们还需要一个办法消除一个状态机的非确定性。
5、消除非确定性
消除ε边算法
我们见到的有穷状态自动机一共有三种：ε-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 ：找到所有有效状态。