NFA中的ε到底有什么用？？
一直搞不明白NFA中的ε转换到底有什么作用？比如下图中的NFA，那两个ε转换有必要吗？？没有ε转换就不叫NFA了，就直接是DFA了 谢答复~~
ε转换存在的意义是什么呢？或者说，它是为了解决哪种问题而存在的？我只是知道ε转换不需要消耗任何符号，但是这能映射到哪种现实情况呢？教材上只是说我们需要有ε转换，但都没说为毛我们要引入这个东西。 首先，ε转换是体系内的东西，并不是引入的。
从正则或者文法转换为FSM的过程中，ε让这种转换过程变得更方便。比如 (ab)+ 代表了一个循环，那么从ab之后的状态到ab之前的状态就是一个ε转换。你说为什么不一开始就让ab之后的状态和ab之前的状态合并为一个状态？注意这个问题中的关键字：“合并”，也就是说从正则到自动机转换算法的角度，ab之后和ab之前分为两个状态很明显容易得多。如果你要一开始就合并也行，那么你的转换算法本质实际上是正则到NFA和NFA到DFA的组合算法，算法的复杂度没有实质的变化。
所以ε是内生的，NFA比DFA更容易生成。 本帖最后由 cjaizss 于 2012-12-24 19:20 编辑
iLRainyday 发表于 2012-12-21 17:26 static/image/common/back.gif
谢答复~~
ε转换存在的意义是什么呢？或者说，它是为了解决哪种问题而存在的？我只是知道ε转换不需要消 ...
引入NFA在这里是正则表达式->DFA的算法中的一环
regex->NFA->DFA是正则表达式的经典算法
页:
[1]