- Construct an initial partition Π of the set of states with two groups: the accepting states F and the non-accepting states S – F
- Apply the repartition procedure to Π to construct a new partition Π new.
- If Π new = Π, let Πfinal= Π and continue with step
- (4). Otherwise, repeat step (2) with Π= Πnew.
for each group G of Π do begin
partition G into subgroups such that two states s and t of G are in the same subgroup if and only if for all input symbols a, states s and t have transitions on a to states in the same group of Π.
replace G in Πnew by the set of all subgroups formed
- Choose one state in each group of the partition Πfinal as the representative for that The representatives will be the states of M’. Let s be a representative state, and suppose on input a there is a transition of M from s to t. Let r be the representative of t’s group. Then M’ has a transition from s to r on a. Let the start state of M’ be the representative of the group containing start state s0 of M, and let the accepting states of M’ be the representatives that are in F.
- If M’ has a dead state d (non-accepting, all transitions to self), then remove d from M’. Also remove any state not reachable from the start state