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

私が理解していないビットは「Distinct(δ(p,a), δ(q,a))」です。遷移関数を理解していると思います。ここで、δ(p,a) = 入力 a で p から到達した状態. ただし、次の DFA を使用します。

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

この表の結果：

imgur.com/Vg38ZDN.png

異なる (δ(b,0), δ(c,0)) は空でないので (c,b) も x としてマークされるべきではありません (d) ?

4

1 に答える 1

0

Distinct(δ(p,a), δ(q,a)) は、δ(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 に答える