پرش به محتوا

# حل تمرین نظریه زبانها و ماشینها/فصل دوم/حل تمرین بخش ۲-۴/حل تمرین ۹

This is a well-known, widely used algorithm that looks at each S ${\displaystyle \in }$ P many fewer times

  W <- {F, Q-F};  P <- {F, Q-F};  // W is the worklist, P the current partition
while ( W  is not empty ) do begin
select and remove S from W;  // S is a set of states
for each ${\displaystyle \alpha }$ in ${\displaystyle \Sigma }$ do begin
let I${\displaystyle \alpha }$ <- ${\displaystyle \delta _{a}^{-1}}$  ( S );  // I${\displaystyle \alpha }$ is set of all states that can reach S on ${\displaystyle \alpha }$
for each R in P such that  R ${\displaystyle \cap }$ Ia is not empty
and R  is not contained in Ia  do begin
partition R  into R1 and R2 such that R${\displaystyle _{1}}$ <- R ${\displaystyle \cap }$ I${\displaystyle \chi }$ ; R2 <- R – R1;
replace R  in P with R1 and R2 ;
if R ${\displaystyle \in }$W  then replace R  with R1 in W and add R2 to W ;
else if || R${\displaystyle _{1}}$ || ≤ || R${\displaystyle _{2}}$ ||
then add add R1 to W ;
else add R2 to W ;
end
end
end