• Input: e-free FA: M = (Q, S, R, s, F)
• Output: DFA:
Md = (Qd, S, Rd, sd, Fd)
• Method:
• Qd := {Q’: Q’ Í Q, Q’ ¹ Æ}; Rd := Æ;
• for each Q’ Î Qd, and a Î S do
begin
Q’’ := {q: p
Î Q’,
pa ® q Î R};
if Q’’ ¹
Æ then Rd := Rd È {Q’a ® Q’’};
end
• sd :=
{s};
• Fd := {F’: F’ Î Qd, F’ Ç F ¹ Æ}.