爱学习，喜欢技术。
| 标题 | 阅读 | 评论 | 转发 | 发布日期 | |
|---|---|---|---|---|---|
| 一个编译器的实现（05）——词法分析(4.扫描器) | 2108 | 0 | 0 | 2011-06-26 | |
| 一个编译器的实现（04）——词法分析(3.最小化DFA) | 3729 | 1 | 0 | 2011-06-26 | |
| 一个编译器的实现（03）——词法分析(2.NFA转DFA) | 4091 | 0 | 0 | 2011-06-26 | |
| 一个编译器的实现（02）——词法分析(1.正则转NFA) | 3687 | 0 | 0 | 2011-06-21 | |
| 一个编译器的实现（01）——初衷与编译概述 | 1834 | 0 | 0 | 2011-06-20 |
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越小越好。
另外，我都两年多没上这个博客了，今天上来居然有留言，真是感到格外惊喜！看来得花点时间写点东西上去。谢谢您啊！
