• Input: e-free FA: M = (Q, S, R, s, F)
• Output: DFA: Md = (Qd, S, Rd, sd, Fd)
       without any inaccessible states
• Method:
• sd := {s}; Qnew := {sd}; Rd = Æ; Qd := Æ; Fd := Æ;
• repeat
let Q’ Î Qnew; Qnew := Qnew – {Q’}; Qd := Qd È {Q’};
for each a Î S do begin
Q’’ := {q: p Î Q’, pa ® q Î R};
if Q’’ ¹ Æ then Rd := Rd È {Q’a ® Q’’};
if Q’’ Ï Qd È {Æ} then Qnew := Qnew  È {Q’’}
     end;
if Q’ Ç F ¹ Æ then Fd := Fd È {Q’}
until Qnew = Æ.
Algorithm II: e-free FA to DFA 2/2
24/44