爱学习,喜欢技术。
标题 | 阅读 | 评论 | 转发 | 发布日期 | |
---|---|---|---|---|---|
【推荐】 我想要的程序开发语言特性——之“面向对象”——之“退化” | 2978 | 0 | 2 | 2014-08-18 | |
用纯函数式思维在Java8下写的一段奇葩程序 | 3905 | 0 | 0 | 2014-07-12 | |
【推荐】 对SNL语言的解释器实现尾递归优化 | 3089 | 0 | 0 | 2014-06-22 | |
天下第一萌程序 | 1811 | 0 | 0 | 2014-05-02 | |
手头上的几本关于实现程序设计语言的书 | 1360 | 0 | 0 | 2014-05-02 | |
简说JAVA8引入函数式的问题。 | 1999 | 0 | 0 | 2014-04-09 | |
词法分析——使用正则文法 | 2321 | 0 | 0 | 2014-04-03 |
naturemickey2014-02-08 09:01
bh8458:上面(04)文中提到的反例:“假设某NFA有三个终态a,b,c,a输入x到b,b输入x到c,c输入x到a,这样的情况不能满足算法1步骤3的任何一个规则,但这三个状态是等价的”该描述不确切,三个状态不一定是等价的。另外,简化DFA和最小DFA是不同概念,最小DFA是简化DFA,但简化DFA不一定是最小DFA。
补充一下:如果a/b/c三个状态的输入x所指向的状态在这三个状态之中,其它输入都指向其它的等价的状态,则a/b/c就是等价的。
其实在哲学上:无论多少个事实支持一个理论都不能证明这个理论是对的,但只要有一个反例就足以证明一个理论是错的。
所以,的确我的描述不准确,但只要这个描述能表示一种情况就可以了。
您说的后半句我同意:简化不是最小化——同时,我们追求的是最小化,因为在描述同一个文法的语言时,DFA的大小是超过NFA的一个数量级的,所以只要对文法的解析时间没有要求,我们都希望DFA越小越好。
另外,我都两年多没上这个博客了,今天上来居然有留言,真是感到格外惊喜!看来得花点时间写点东西上去。谢谢您啊!