DFA алгоритм минимизации понимание

Question

Я пытаюсь понять этот алгоритм алгоритма минимизации DFA в http://www.cs.umd.edu/class/fall2009/cmsc330/lectures/discussion2.pdf, где он говорит:

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 (б (р, а), δ (q, a)) «Я думаю, что я понимаю функцию перехода, где δ (p, a) = любое состояние достигнуто из p с входом a. но со следующими DFA:

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

в результате в этой таблице:

imgur.com/Vg38ZDN.png

не должен (с, б) также может быть отмечен как х, так как (δ (b, 0), δ (c, 0)) не пусто (d)?

Answer 1

Отдельный (δ (p, a), δ (q, a)) будет только непустым, если δ (p, a) и δ (q, a) различны. В вашем примере δ (b, 0) и δ (c, 0) равны d. Отличительный (d, d) пуст, так как не имеет смысла, чтобы d отличался от самого себя. Поскольку Distinct (d, d) пуст, мы не отмечаем Distinct (c, b).

В целом, Distinct (p, p), где p - состояние, всегда будет пустым. Еще лучше, мы не считаем это, потому что это не имеет смысла.