we need to derive the minimization algorithm is to determine the equivalence classes. But determining if two states are equivalent isnt straightforward because the definition requires us to check infinitely many strings! Heres the trick: instead of checking for pairs of equivalent states, we instead look for pairs of states that are NOT equivalent! In part 5 we showed that ~ (,)~(,). The contrapositive is (,) (,) . So, starting with pairs of states in which one state is an accept state and the other is not, we can work backwards to determine all inequivalent pairs of states. Here is the final algorithm: 1. Make a table of pairs of states {,}. Initially leave all entries unmarked.1 2. Mark each entry {,} if ( ) ( ) 3. Scan the entire table, and if there is an unmarked pair {,} such that {(,),(,)} is marked for some , then mark {,}. If no mark was created during the scan, go to step 4. Otherwise repeat step 3. 4. After the final scan, if any pair {,} is unmarked then merge , into one state. If pairs {,} and {,} are both unmarked, merge ,, into one state.

5. Use this to define , the equivalent minimum state DFA as follows: if there was a transition labeled from state to state in the original DFA, then draw a transition labeled from the state that was merged into to the state that was merged into. The new start state is the one that the original start state got merged into.

Prove that the above algorithm is sound and complete. In other words, show that a pair of states is marked if and only if the two states are not equivalent. Hint: use induction.