有效状态就是在完成了消除ε边算法之后仍然存在的状态。我们可以在开始整个算法 之前就预先计算出所有有效状态。有效状态的特点是存在非ε边的输入。同时，起始状态也是一个有效状态。结束状态不一定是有效状态，但是如果存在一个有效状 态可以仅通过ε边到达结束状态的话，那么这个状态应该被标记为结束状态。因此对一个ε-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。
从NFA 到DFA