• Input: DFA: M = (Q, S, R, s, F)
• Output: DFA: Mt = (Qt, S, Rt, s, F)
• Method:
• Q0 := F; i := 0;
• repeat
      i := i + 1;
    Qi := Qi-1 È {q: qa ® p Î R, a Î S, p Î Qi-1};
until Qi = Qi-1;
• Qt := Qi;
• Rt := {qa ® p: qa ® p Î R,  p, q Î Qt , a Î S}.
Algorithm: Removal of nont. states
29/44