在这个最小化的DFA中，无法到达的状态能被移除吗？
在这个最小化的DFA中，无法到达的状态能被移除吗？
提问于 2019-10-17 15:41:47
所以这是DFA的问题，需要最小化。
这个问题的答案是这个，正如你所看到的，DFA现在被最小化了。
，我的问题是：如您所见，最小化的DFA有一个状态q7，它从一开始或初始状态就无法到达。那么，为什么他们在最后的答案中显示状态q7，难道不应该删除不可访问的状态以使这个dfa最小化。
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-07-18 15:14:16
如果仔细观察，所有的状态( q4、q5、q6、q7 )都无法从初始状态q0 (而不仅仅是q7 )到达，因此应该删除所有这4种状态。我的解决方案将从q0、q1、q2、q3开始，然后遵循还原过程。
我认为答案应该是：
Stack Overflow用户
发布于 2019-10-21 17:32:30
让我们实际一点。除了定义和构造之外，对应于给定DFA的最小DFA应该是一个DFA，它接受相同的语言，并且有尽可能少的状态。DFA最小化的任何其他定义都没有这个定义那么有用。在此情况下，您的问题的答案是明确的，q7不能处于最小化的DFA中，因为没有q7的DFA接受相同的语言，并且有更少的状态。我们可以争论一个特定的最小化过程是否会移除它，或者任何无穷大的东西，但是这种状态真的必须去。另一个必须去做的原因是，Myhill-Nerode定理告诉我们，这种语言的最小DFA必须有相同数量的状态，对于这种语言来说，就像我们在不可区分关系上做等价类一样。因为没有字符串导致q7，所以它根本就没有等价类，而且肯定不会有一个新的类。
TL;DR - q7不是与给定的DFA相对应的最小DFA状态.做你想做的事。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58436297
复制相关文章
相似问题
腾讯云开发者
