我搜索了谷歌，在许多页面中都给出了最小化 DFA 死状态或陷阱状态被删除。我的问题是，如果某些转换未定义，它怎么可能仍然是 DFA。那你说的人呢？
问问题
9076 次
3 回答
7
即使是最小的 DFA 也必须包括死状态；否则，它们要么 (a) 不是 DFA，要么 (b) 不接受与非最小对应物相同的语言。例如，语言 {a} 在字母 {a, b} 上的最小 DFA 必须具有 3 个状态：一个可以看到 a 并接受的起始状态；如果您看到其他任何内容，您会拒绝的接受状态；如果你看到 ab 或任何处于接受状态的东西，你就会去死状态。
从未听说过从最小 DFA 中省略死状态。亵渎神明！
于 2012-02-04T13:52:58.337 回答
0
在“最小”版本中没有删除死状态，但是是的，它们在 DFA 的“反转”期间丢失了（可能你把术语弄混了）
于 2013-09-04T17:52:54.363 回答
0
@PrashantBhardwaj：我还认为应该包括它（死状态和相应的死动作），因为包括它会完成 DFA，即，通过考虑它，我们不会在最小化 DFA 中对特定状态进行任何匿名移动。
仍然，这个问题没有答案？最后，我们应该包括它还是不包括它？有人可以证明吗？
于 2015-09-07T05:37:37.940 回答