• 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 = Æ.