This is an old revision of the document!
Minimization of Deterministic Finite State Machines
We consider deterministic finite state machine .
Goal: build a state machine with the least number of states that accepts the language .
This is the process of minimization of .
We say that state machine distinguishes strings and iff it is not the case that ( iff ).
Step 1: Remove unreachable states
We first discard states that are not reachable from the initial state–such states are useless. In resulting machine, for each state there exists a string such that , let one such string of minimal length.
(Main) Step 2: Compute Non-Equivalent States
We wish to merge states and into same group as long as they “behave the same” on all future strings , i.e. \[
\delta(q,w) \in F \mbox{ iff } \delta(q',w) \in F
\] for all .
If the condition above holds, we called states equivalent. If the condition does not hold, we call states , non-equivalent. States and are -non-equivalent if it is not the case that ().
Observe that
- if and then (taking to be empty string) we conclude that and are non-equivalent.
- if and are non-equivalent and we have , for some symbol , then and are non-equivalent.
These two observations lead to an iterative algorithm for computing non-equivalence relation
- initially put
- repeat until no more changes: if for some states there is such that , then
Step 3: Merge States that are not non-equivalent
Relation is an equivalence relation and the 'factor automaton' obtained by merging equivalent states is well defined.
This is the minimal automaton.
Correctness of Minimization
Clearly, this algorithm terminates because in worst case all states become non-equivalent. We will prove below that the resulting value is the non-equivalence relation.
By induction, we can easily prove that if , then and are non-equivalent. Similarly we can show that if and are -non-equivalent for of length , then by step of the algorithm. Because the algorithm terminates, this completes the proof that is the non-equivalence relation.
Consequently, is the equivalence relation. From the definition of this equivalence it follows that if two states are equivalent, then so is the result of applying to them. Therefore, we have obtained a well-defined deterministic automaton.
Minimality of Constructed Automaton
Note that if two states are non-equivalent, there is such that states and have different acceptance, so distinguishes and . Now, if we take any other state machine with , it means that , otherwise would not distinguish and . So, if there are pairwise non-equivalent states in , then a minimal finite state machine for must have at least states. Note that if the algorithm constructs a state machine with states, it means that had equivalence relations, which means that there exist non-equivalent states. Therefore, any other deterministic machine will have at least as many states, proving that the constructed machine is minimal.