论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2012-12-20 22:44 |只看该作者 |倒序浏览

一直搞不明白NFA中的ε转换到底有什么作用？比如下图中的NFA，那两个ε转换有必要吗？？

文库|博客

cjaizss

版主

论坛徽章:: 3

2楼 [报告]

发表于 2012-12-21 10:42 |只看该作者

没有ε转换就不叫NFA了，就直接是DFA了

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

iLRainyday

丰衣足食

论坛徽章:: 0

3楼 [报告]

发表于 2012-12-21 17:26 |只看该作者

谢答复~~

ε转换存在的意义是什么呢？或者说，它是为了解决哪种问题而存在的？我只是知道ε转换不需要消耗任何符号，但是这能映射到哪种现实情况呢？教材上只是说我们需要有ε转换，但都没说为毛我们要引入这个东西。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

sonicling

家境小康

论坛徽章:: 0

4楼 [报告]

发表于 2012-12-24 18:02 |只看该作者

首先，ε转换是体系内的东西，并不是引入的。

从正则或者文法转换为FSM的过程中，ε让这种转换过程变得更方便。比如 (ab)+ 代表了一个循环，那么从ab之后的状态到ab之前的状态就是一个ε转换。你说为什么不一开始就让ab之后的状态和ab之前的状态合并为一个状态？注意这个问题中的关键字：“合并”，也就是说从正则到自动机转换算法的角度，ab之后和ab之前分为两个状态很明显容易得多。如果你要一开始就合并也行，那么你的转换算法本质实际上是正则到NFA和NFA到DFA的组合算法，算法的复杂度没有实质的变化。

所以ε是内生的，NFA比DFA更容易生成。

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

cjaizss

版主

论坛徽章:: 3

5楼 [报告]

发表于 2012-12-24 19:19 |只看该作者

本帖最后由 cjaizss 于 2012-12-24 19:20 编辑

iLRainyday 发表于 2012-12-21 17:26
谢答复~~

ε转换存在的意义是什么呢？或者说，它是为了解决哪种问题而存在的？我只是知道ε转换不需要消 ...

引入NFA在这里是正则表达式->DFA的算法中的一环
regex->NFA->DFA是正则表达式的经典算法

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

返回列表

Chinaunix › 论坛 › 程序设计 › CPU与编译器 › NFA中的ε到底有什么用？？

NFA中的ε到底有什么用？？ [复制链接]