finite-automata - DFA最小化算法理解

Question

我试图在http://www.cs.umd.edu/class/fall2009/cmsc330/lectures/discussion2.pdf 上理解这个算法 DFA 最小化算法，它说：

while until there is no change in the table contents:
    For each pair of states (p,q) and each character a in the alphabet:
        if Distinct(p,q) is empty and Distinct(δ(p,a), δ(q,a)) is not empty:
            set distinct(p,q) to be x

我不明白的一点是“不同（δ（p，a），δ（q，a））”我想我理解转换函数，其中δ（p，a）=输入a从p达到的任何状态. 但使用以下 DFA：

http://i.stack.imgur.com/arZ8O.png

生成此表：

imgur.com/Vg38ZDN.png

不应该 (c,b) 也被标记为 x 因为 distinct(δ(b,0), δ(c,0)) 不为空 (d) ？

Answer 1

仅当 δ(p,a) 和 δ(q,a) 不同时， Distinct(δ(p,a), δ(q,a)) 才会是非空的。在您的示例中，δ(b,0) 和 δ(c,0) 都是 d。Distinct(d, d) 是空的，因为 d 与自身不同是没有意义的。由于 Distinct(d, d) 为空，我们不标记 Distinct(c, b)。

一般来说，当 p 是一个状态的 Distinct(p, p) 将始终为空。更好的是，我们不考虑它，因为它没有意义。