• Input: WSFA  M = (Q, S, R, s, F)
• Output: Minimum-State FA Mm = (Qm, S, Rm, sm, Fm)
• Method:
• Qm = {{p: p Î F}, {q: q Î Q – F}};
• repeat
if there exist  X  Î Qm,  d Î S,  X1, X2 Ì X such that
    X = X1 È X2, X1 Ç X2 = Æ and
   {q1: p1 Î X1, p1d ® q1 Î R} Í Q1, Q1 Î Qm,
   {q2: p2 Î X2, p2d ® q2 Î R} Ç Q1 = Æ
then divide X into X1 and X2 in Qm
until no division is possible;
• Rm = { Xa ® Y: X, Y Î Qm, pa ® q Î R, p Î X, q Î Y, a Î S};  
• sm = X with s Î X;  Fm := {X: X Î Qm, X Ç F ¹ Æ}.
Algorithm: WSFA to Min-State FA
39/44