DFA 최소화 알고리즘을 이해

Question

내가 말하는 곳 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) = 입력이있는 p로부터 어떤 상태에 도달했는지에 대한 전이 함수를 이해한다고 생각한다. 그러나 다음과 DFA :

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

표 결과 :

imgur.com/Vg38ZDN.png

이 (c, b)도 X 보낸으로 표시되어서는 안된다

distinct (δ (b, 0), δ (c, 0))는 비어 있지 않다 (d)?

Answer 1

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)는 항상 비어 있습니다. 더 나은 아직, 우리는 그것을 이해하지 않기 때문에 그것을 고려하지 않습니다.