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, executable 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
).
Minimization Algorithm
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 (
).
Two states are non-equivalent iff they are -non-equivalent for some string
.
Observe that
- if
and
then
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
(only final and non-final states are initially non-equivalent)
- repeat until no more changes: if
and there is
such that
, then
\[
\nu := \nu \cup \{(r,r')\}
\]
Step 3: Merge States that are not non-equivalent
Relation is an equivalence relation
. We define the 'factor automaton' by merging equivalent states:
= \{ \{ y \mid x \sim y \} \mid x \in F \}
\nu
(*)
(q,q') \in \nu
q
q'
q
q'
w
w
k
(q,q') \in \nu
k
\nu
Q^2 \setminus \nu
\delta
w
\delta(q_0,s_q w)
\delta(q_0,s_{q'} w)
M
s_q w
s_{q'}w
M' = (\Sigma,Q',\delta',q'_0,F')
L(M')=L(M)
\delta'(q'_0,s_q) \neq \delta'(q'_0,s_{q'})
M'
s_q w
s_{q'} w
K
M
L(M)
K
K
Q^2 \setminus \tau
K
K
K$ states, proving that the constructed machine is minimal.