• 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 ¹ Æ}.