2

我试图在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) ?

4

1 回答 1

0

仅当 δ(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) 将始终为空。更好的是,我们不考虑它,因为它没有意义。

于 2013-06-10T05:35:15.293 回答