3.7. Minimizing the Number of States in a DFA¶
3.7.1. Minimizing the Number of States in a DFA¶
Unfortunately, this is not an algorithm, since we cannot actually test on all input strings if the language is infinite.
But remember the definition for \(\delta^*(p, w)\). Look at things this way: It is telling us that we don’t care about the prior history before we got to the current state with whatever remains of the input.
So, we can look at each transition out of two subsets being considered, and verify that they lead to “equivalent” places (which is not the same as leading to the same state in the non-minimized machine).
We will start with the maximum possible joining of states as a potential equivalence class, and see if we find evidence that forces us to break them apart as we consider the various transitions.
We will build a tree, whose root has all states in the original machine. The first step will always be to split the states into the subset of non-final vs. the subset of final states, so these are the children of the root. We then look at some current leaf node of the tree, and check the transitions from each of the states in that leaf. We test a given character against the states in that subset to see if they all go to the same subset. Split them up when they do not go to the same place.
3.7.2. Minimization Example 1¶
The following slideshow presents, step-by-step, the process of minimizing the DFA.
