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

ویکی‎کتاب، کتابخانهٔ آزاد
پرش به ناوبری پرش به جستجو

This is a well-known, widely used algorithm that looks at each S 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 in do begin
let I <- ( S ); // I is set of all states that can reach S on
for each R in P such that R Ia is not empty
and R is not contained in Ia do begin
partition R into R1 and R2 such that R <- R I ; R2 <- R – R1;
replace R in P with R1 and R2 ;
if R W then replace R with R1 in W and add R2 to W ;
else if || R || ≤ || R ||
then add add R1 to W ;
else add R2 to W ;
end
end
end