免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2468 | 回复: 4

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

论坛徽章:
0
发表于 2012-12-20 22:44 |显示全部楼层
一直搞不明白NFA中的ε转换到底有什么作用?比如下图中的NFA,那两个ε转换有必要吗??

图像 1.jpg

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2012-12-21 10:42 |显示全部楼层
没有ε转换就不叫NFA了,就直接是DFA了

论坛徽章:
0
发表于 2012-12-21 17:26 |显示全部楼层
谢答复~~

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

论坛徽章:
0
发表于 2012-12-24 18:02 |显示全部楼层
首先,ε转换是体系内的东西,并不是引入的。

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

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

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2012-12-24 19:19 |显示全部楼层
本帖最后由 cjaizss 于 2012-12-24 19:20 编辑
iLRainyday 发表于 2012-12-21 17:26
谢答复~~

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

引入NFA在这里是正则表达式->DFA的算法中的一环
regex->NFA->DFA是正则表达式的经典算法
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP