1

当我们想要最小化 DFA 时，首先我们划分最终状态和非最终状态。然后我们将这些状态划分为多个分区，直到每个分区中的所有状态都属于同一个等价类。现在我的问题是假设我们有dfa 中的死状态，那么它应该进入非最终状态的分区还是单独的分区（仅包含死状态）？另外请告诉我该死状态是否应该算作最小化状态之一dfa?

4

1 回答 1

3

死状态进入非最终状态集合，因为它不是接受状态。在最小化算法期间，您就像对待任何其他状态一样对待它。当你完成后，如果你的 DFA 需要一个死状态，它应该有一个死状态作为它的状态之一。一些常规语言需要死状态，但算法足够“智能”以确保它们被包含在内。

希望这可以帮助！

于 2013-10-14T06:54:29.127 回答