在教科书中，通常把确定的有穷状态自动机(有穷状态自动机也就是本文讨论的这种状态机)称为DFA，把非确定的有穷状态自动机称为NFA，把带有ε边的非确定的状态机称为ε-NFA。下文中也将采用这几个术语来指示各种类型的有穷状态自动机。
在刚刚接触到ε边的时候，一个通常的疑问就是这种边存在的理由。事实上如果是人 直接画状态机的话，有时候也可以直接画出一个确定的状态机，复杂一点的话也可以画出一个非确定的状态机，在有些极端的情况下我们需要使用ε边来更加简洁的 表示我们的意图。不过ε边存在的最大的理由就是：我们可以通过使用ε边来给出一个简洁的算法把一个正则表达式转换成ε-NFA。
4、从正则表达式到ε-NFA
通过第二节所描述的内容，我们知道一个正则表达式的基本元素就是字符集。通过对 规则的串联、并联、重复、可选等操作，我们可以构造除更复杂的正则表达式。如果从正则表达式构造状态机的时候也可以用这几种操作对状态图进行组合的话，那 么方法将会变得很简单。接下来我们将一一对这5个构造正则表达式的方法进行讨论。使用下文描述的算法构造出来的所有ε-NFA都有且只有一个结束状态 。
1 ：字符集
字符集是正则表达式最基本的元素，因此反映到状态图上，字符集也会是构成状态图的基本元素。对于字符集C，如果有一个规则只接受C的话，这个规则对应的状态图将会被构造成以下形式：
图4.1
这个状态图的初始状态是Start，结束状态是End。Start状态读入字符集C跳转到End状态，不接受其他字符集。
2 ：串联
如果我们使用A⊙B表示规则A和规则B的串联，我们可以很容易的知道串联这个操 作具有结合性，也就是说(A⊙B)⊙C=A⊙(B⊙C)。因此对于n个规则的串联，我们只需要先将前n-1个规则进行串连，然后把得到的规则看成一个整 体，跟最后一个规则进行串联，那么就得到了所有规则的串联。如果我们知道如何将两个规则串联起来的话，也就等于知道了如何把n个规则进行串联。
为了将两个串联的规则转换成一个状态图，我们只需要先将这两个规则转换成状态 图，然后让第一个状态的结束状态跳转到第二个状态图的起始状态。这种跳转必须是不读入字符的跳转，也就是令这两个状态等价。因此，第一个状态图跳转到了结 束状态的时候，就可以当成第二个状态图的起始状态，继续第二个规则的检查。因此我们使用了ε边连接两个状态图：
图4.2
3 ：并联
并联的方法跟串联类似。为了可以在起始状态读入一个字符的时候就知道这个字符可 能走的是并联的哪一些分支并进行跳转，我们需要先把所有分支的状态图构造出来，然后把起始状态连接到所有分支的起始状态上。而且，在某个分支成功接受了一 段字符串之后，为了让那个状态图的结束状态反映在整个状态图的结束状态上，我们也把所有分支的结束状态都连接到大规则的结束状态上。如下所示：
图4.3
4 ：重复
对于一个重复，我们可以设立两个状态。第一个状态是起始状态，第二个状态是结束状态。当状态走到结束状态的时候，如果遇到一个可以让规则接受的字符串，则再次回到结束状态。这样的话就可以用一个状态图来表示重复了。于是对于重复，我们可以构造状态图如下所示：