• Vstup: KA bez e-přechodů: M = (Q, S, R, s, F)
• Výstup: DKA:
Md = (Qd, S, Rd, sd, Fd)
bez nedostupných stavů
• Metoda:
• sd
:= {s}; Qnew :=
{sd}; Rd = Æ; Qd := Æ; Fd := Æ;
• repeat
nechť 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 = Æ.