DFA Minimization
Myhill-Nerode Method
CMPE 322/327 Theory of Computation 1
DFA Minimization
• Every DFA defines a regular language
• In general, there can be many DFAs for a given regular language.
• These DFAs accept the same regular language.
– Language: The set of strings of 0’s and 1’s containing even number of 1’s
0 0 0 0 0
1 1 1
1 1
A minimal DFA
• In practice, we are interested in the DFA with the minimal number of states.
– Use less memory
– Use less hardware (flip-flops)
• We can find a minimal DFA for any given DFA and their languages are equal.
CMPE 322/327 Theory of Computation 3
Indistinguishable States
• Let A = (Q, , ,q0,F) be a DFA, and {p,q} Q, we say that p and q are
indistinguishable (equivalent) states if:
CMPE 322/327 Theory of Computation 4
Indistinguishable States
• Indistinguishable states behave the same for all possible strings.
– So, we do not need all of states from a set of indistinguishable states.
– We can eliminate all of them by keeping only one of them to represent that set of
indistinguishable states.
• Indistinguishability is an equivalence relation:
– Reflexive: Each state is indistinguishable from itself
– Symmetric: If p is indistinguishable from q, then q is indistinguishable from p
– Transitive: If p is indistinguishable from q, and q is indistinguishable from r, then
p is indistinguishable from r.
CMPE 322/327 Theory of Computation 5
Indistinguishable States
• An equivalence relation on a set of states Q induces a partitioning 1, 2,…, k such
that:
CMPE 322/327 Theory of Computation 6
Finding Distinguishable States –
Table Filling Algorithm
• We can compute distinguishable states with an inductive table filling algorithm.
Basis:
• Any non-accepting state is distinguishable from any accepting state.
Induction:
• States p and q are distinguishable if there is some input symbol a such that (p,a)
is distinguishable from (q,a).
• All other pairs of states are indistinguishable, and can be merged appropriately.
CMPE 322/327 Theory of Computation 7
Finding Distinguishable States –
Table Filling Algorithm
CMPE 322/327 Theory of Computation 8
Minimization of DFA
Table Filling Algorithm
• We can also use table filling algorithm to minimize a DFA by merging all equivalent
states.
• That is, we replace a state p with its equivalence class found by the table filling
algorithm.
• Equivalence Classes: = { 1, 2,…, k}
– So, each equivalence class i will be a state in the minimized DFA.
CMPE 322/327 Theory of Computation 9
Table Filling Algorithm: Example 1
0
q x • p is distinguishable from q
0 q
p
r x and r by basis, mark them
1 1 p q
1
0
r
• Both q and r go to p with 0, so
q x no string beginning with 0 will
r x distinguish them
• Starting in either q and r , an
p q input of 1 takes us to either,
• so they are indistinguishable.
• Equivalence relation partitions (equivalence
classes): { {p}, {q,r} }
CMPE 322/327 Theory of Computation 10
Table Filling Algorithm: Example 1
p
0 q • Equivalence relation partitions (equivalence
classes): { {p}, {q,r} }
1 1
1 • q and r are indistinguishable.
0
r
p
0,1 {q,r} 1
DFA with minimal states
CMPE 322/327 Theory of Computation 11
Minimization of DFA
Table Filling Algorithm: Example 2
CMPE 322/327 Theory of Computation 12
Minimization of DFA
Table Filling Algorithm: Example 2
PASS 0: Distinguish accepting states from
non-accepting states
• C is only accepting state, it is distinguishable
from all other non-acceptingt states.
CMPE 322/327 Theory of Computation 13
Minimization of DFA
Table Filling Algorithm: Example 2
PASS 1: Consider column A
CMPE 322/327 Theory of Computation 14
Minimization of DFA
Table Filling Algorithm: Example 2
PASS 1: Consider column B
CMPE 322/327 Theory of Computation 15
Minimization of DFA
Table Filling Algorithm: Example 2
PASS 1: Consider column D
CMPE 322/327 Theory of Computation 16
Minimization of DFA
Table Filling Algorithm: Example 2
PASS 1: Consider columns E, F, G
CMPE 322/327 Theory of Computation 17
Minimization of DFA
Table Filling Algorithm: Example 2
PASS 2: Consider columns A, B, D
CMPE 322/327 Theory of Computation 18
Minimization of DFA
Table Filling Algorithm: Example 2
PASS 3: Consider columns A, B, D
No new marked states in PASS 3. We are done, and
we found all distinguishable states (marked ones).
CMPE 322/327 Theory of Computation 19
Minimization of DFA
Table Filling Algorithm: Example 2
Equivalence Classes:
{ {A,E}, {B,H}, {C}, {D,F}, {G} }
CMPE 322/327 Theory of Computation 20
Minimization of DFA
Table Filling Algorithm: Example 2
Equivalence Classes:
{ {A,E}, {B,H}, {C}, {D,F}, {G} }
CMPE 322/327 Theory of Computation 21
Is the Minimized DFA Really Minimal?
• Let M be the minimized DFA found by the table filling algorithm and assume that its
states P = {p 0,…,p m} and its transition function is .
• Suppose there is an equivalent DFA M 1 with transition function 1but with fewer
states Q = {q0,…,qn} where n<m.
• Since all states of M are distinguishable (since M is minimal), there must be distinct
,w ) = p for all i.
strings w1,…,wm such that δ(p 0 i i
CMPE 322/327 Theory of Computation 22
Is the Minimized DFA Really Minimal?
• Since M has fewer states than M, then there must be strings w and w j among distinct
strings w ,…,w such that δ (q ,w ) = δ (q ,w ) (pigeonhole principle)
• Since p and p are distinguishable, there must be some string x such that
CMPE 322/327 Theory of Computation 23
Testing Equivalence of Regular Languages
with Table Filling Algorithm
1st Approach to Test Equivalence:
– Minimize their DFAs,
– Check whether they are isomorphic (ie. they are same with renaming states)
2nd Approach to Test Equivalence:
– Let L and M be regular languages, to test whether L = M
– Create DFAs for both L and M
– Imagine the DFA that is the union of the two DFA's (never mind there are two
start states)
– If the table filling algorithm says that the two start states are distinguishable, then
L M, otherwise L = M.
CMPE 322/327 Theory of Computation 24
Testing Equivalence of Regular Languages
with Table Filling Algorithm - Example
• Since A and C are equivalent,
these two DFAs are equivalent.
• Their languages are also equivalent.
CMPE 322/327 Theory of Computation 25
