私はこのアルゴリズムを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) ?