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
.
- we obtain a space-efficient representation of a regular 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
states, proving that the constructed machine is minimal.