DFA minimisation

Since we are interested in translating a DFA into a program, we will want to ensure that this program is as efficient as possible. In automata terms, one aspect of this will be to ensure that the constructed DFA has as few states as possible. This is achieved by an algorithm known as DFA minimisation.

We take the ``optimistic'' approach: we start by assuming that all states are actually the same, and only distinguish those which we can prove are different. As for subset construction, the states of the minimised DFA will be sets of states from the original DFA; these will be states that we couldn't tell apart!

Two states are different if:

• one is a final state and the other isn't, or
• the transition function maps them to different states, based on the same input character
  

We base our algorithm on partitioning the states using this criterion.

1. Initially start with two sets of states: the final, and the non-final states.
2. For each state-set created by the previous iteration, examine the transitions for each state and each input symbol. If they go to a different state-set for any two states, then these should be put into different state-sets for the next iteration.
3. We are finished when an iteration creates no new state-sets.