这个DFA是否已经被最小化了？

Question

我试图通过table-填充方法最小化这个 DFA:

所以这是我为这个图做的 table:

由此可以得出结论table图形已经最小化了，不需要继续
对吗？

Answer 1

我们可以使用 Myhill-Nerode 来检查这个 DFA 的状态是否对应于不可区分关系下的唯一等价 classes。

导致状态 1 的字符串可以跟在语言中的任何字符串之后，并且是我们看到的第一个字符串，因此我们必须在最小 DFA 中拥有这样的状态。

导致状态 2 的字符串不能后跟 a 以获得可接受的字符串，因此状态 2 对应于一个 class 不同于状态 1 的。

状态 3 未接受，因此必须对应于不同于状态 1 和状态 2 的 class。

状态 4 不接受，因此 class 不能与状态 1 或状态 2 相同。导致状态 4 的字符串不能后跟 b 以获取语言中的字符串，因此状态 4 也不同于状态 3。

状态 5 也不接受，因此它与状态 1 和状态 2 不同。导致状态 5 的字符串后面可以跟 a 以获取语言中的字符串，因此状态 5 也不同于状态 3和状态 4.

状态6不接受，所以它也不同于状态1和状态2。它后面可以跟a或b来得到语言中的字符串，所以它不同于状态3、4和5.

状态 7 正在接受，因此它不同于状态 3、4、5 和 6。通往状态 7 的字符串后面可以跟 a 或 aa 以获取语言中的字符串，因此状态 7 不同于分别为状态 2 和状态 1。

因为所有状态都是可区分的，所以 DFA 对于它接受的任何语言都是最小的。