爱学习，喜欢技术。
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越小越好。
另外，我都两年多没上这个博客了，今天上来居然有留言，真是感到格外惊喜！看来得花点时间写点东西上去。谢谢您啊！
