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