爱学习，喜欢技术。
发布时间：2011-06-26 20:45:56
檀凤琴1998[3]中的算法是比较简单的，但那个算法有错误——有些情况的NFA并不能用她的算法来进行最小化，可能某些构造NFA的方法可以保证不会出现那些不适用于这个算法的NFA，但她没有证明，也没看到其它人证明过，我也没打算去证明它，所以我们这里不用她的算法。但可以借鉴参考，那个算法实现起来要比下面AMRJ2010[1]和MLS.........【阅读全文】
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越小越好。
另外，我都两年多没上这个博客了，今天上来居然有留言，真是感到格外惊喜！看来得花点时间写点东西上去。谢谢您啊！
