L9- ToC

DFA Minimization

Course Instructors:
Div 1: Praveen Pawar (Div 1)
Div 2: Jibi Abraham (Div 2)

1
 Polling - 1
 What is 0 transition of the converted DFA start
state?
A. ᵠ

B. [A]

C. [B]

D. [C]

E. [AB]

F. [BC]

G. [AC]

H. [ABC] 2
 DFA Minimization
 Are these two DFAs equivalent?
 What is the language?
 DFA Minimization: The Idea
• “Minimal”?
• DFA with Minimal number of states

• Equate and collapse states having same

behavior

4
 Equivalent States
Build equivalence relation on states:
pq  (w  S*, ̂ (p, w)F  ̂ (q, w)F)
pq  (w  S*, ̂(p, w)∉F  ̂ (q, w) ∉ F)

i.e., iff for every string w, one of the following is true:

w w
p p
or
w w
q q

5
 Distinct States
 If two states are not equivalent, then they are distinct

p≠q  (w  S*, ̂ (p, w)F and ̂ (q, w) ∉ F)

p≠q  (w  S*, (p, w)∉F and ̂ (q, w)  F)
̂

 Two states p and q are distinct if

 p in F and q not in F or vice versa, or
 for some α in Σ, δ(p, α) and δ(q, α) are distinct

6
 Example - 1

 δ(q1, 0) = q2, δ(q2, 0) = q1 both are non final and

δ(q1, 1) = δ(q2, 1) = q4 both to final, q1 and q2
are equivalent
 δ(q0, 0) = q0 δ(q3, 0) = q2 both are non final, but
δ(q0, 1) = q3 and δ(q3, 1) = q4 (non final and
final), q0 and q3 are distinct 7
 DFA Minimization: Algorithm
 Build table to compare each unordered pair of
distinct states p, q

 Each table entry has

 a “mark” as to whether p and q are known to be

not equivalent (distinct)

 a list of entries, recording dependences: “If this

entry is later marked, also mark these.”

8
 DFA Minimization: Algorithm
1. Create lower-triangular table, initially blank (unmarked and
with no dependences)

2. For every pair of states (p, q):

 If p is final and q is not, or vice versa, then mark (p, q)

3. Loop until no change for an iteration: For each unmarked

pair p, q and input symbol a:
1. Let r = (p, a), s = (q, a).
2. If (r, s) marked, then mark (p, q)

4. Combine all the unmarked pairs of states (p, q) and mark

them as a single state

5. Delete inaccessible (unreachable) states 9

 Example-1
Minimize the following DFA

10
 Example-1

q1

q2

q3

q4
1. Initialize table entries:
Unmarked, empty list q0 q1 q2 q3

11
 Example-1

q1

q2

q3

q4
2. Mark pairs of final and
non-final states q0 q1 q2 q3

12
 Example-1

q1
(q0,a) ? (q1,0) = ?
(q0,b) ? (q1,b) = ?
q2

q3

q4
3. For each unmarked
pair and symbol, … q0 q1 q2 q3

13
 Example-1

(q0,a) ? (q1,a) = ?
q1
(q0,b) ? (q1,b) = ?

q2 State (q1, q1) marked?

State (q2, q3) marked?
q3

q4
3. For each unmarked
pair and symbol, … q0 q1 q2 q3

14
 Example-1

(q0,a) ? (q2,a) = ?
q1
(q0,b) ? (q2,b) = ?

q2 State (q1, q1) marked?

State (q2, q2) marked?
q3

q4
3. For each unmarked
pair and symbol, … q0 q1 q2 q3

15
 Example-1

(q0,a) ? (q3,a) = ?
q1
(q0,b) ? (q3,b) = ?

q2 State (q1, q1) marked?

State (q2, q4) marked?
q3

q4
3. For each unmarked
pair and symbol, … q0 q1 q2 q3

16
 Example-1

(q1,a) ? (q2,a) = ?
q1
(q1,b) ? (q2,b) = ?

q2 State (q1, q1) marked?

State (q3, q2) marked?
q3

q4
3. For each unmarked
pair and symbol, … q0 q1 q2 q3

17
 Example-1

(q1,a) ? (q3,a) = ?
q1
(q1,b) ? (q3,b) = ?

q2 State (q1, q1) marked?

State (q3, q4) marked?
q3

q4
3. For each unmarked
pair and symbol, … q0 q1 q2 q3

18
 Example-1

(q2,a) ? (q3,a) = ?
q1
(q2,b) ? (q3,b) = ?

q2 State (q1, q1) marked?

State (q2, q4) marked?
q3

q4
3. For each unmarked
pair and symbol, … q0 q1 q2 q3

19
 Example-1
({q0, q2}, a)  {q1, q1}
({q0, q2}, b)  {q2, q2}

({q0, q1}, a)  {q1, q1} q1

({q0, q1}, b)  {q2, q3}
q2
({q1, q2}, a)  {q1, q1}
({q1, q2}, b)  {q3, q2} q3

q4

q0 q1 q2 q3

3. Loop until no change for an iteration:

a. For each unmarked
pair and symbol, …
20
 Example-1

q1

q2

q3

q4
4. Combine unmarked
pairs of states q0 q1 q2 q3

q0 and q2 equivalent, all other states are distinct

21
 Example-1
4. Combine unmarked pairs of states
q0 and q2 equivalent, all other states are distinct
5. Delete unreachable states: NIL

22
 Polling - 2
Minimal DFA is free from
a. Dead States, Unreachable States

b. Dead States, Equal States

c. Equal States, Unreachable States

d. Dead, unreachable and equal states

23
 Example-2
0 1

0 1 0
a b c d b
1 0 1
0 1
1 1 0
e f g h c
1 0

0
d

e
1. Initialize table entries:
Unmarked, empty list f

a b c d e f g
24
 DFA Minimization: Example
0 1

0 1 0
a b c d b
1 0 1
0 1
1 1 0
e f g h c
1 0

0
d

e
2. Mark pairs of final and
non-final states f

a b c d e f g
25
 DFA Minimization: Example
(b,0)  ? (a,0) = ?
1
0 (b,1)  ? (a,1) = ?
0 1 0
a b c d State (g, b) marked?
0 1 b
1 State (c, f) marked?
0 1
1 1 0
e f g h c
1 0

0
d

e
3. For each unmarked
pair and symbol, … f

a b c d e f g
26
 DFA Minimization: Example
0 1

0 1 0
a b c d b
1 0 1
0 1
1 1 0
e f g h c
1 0

0
d

e
4. Coalesce unmarked
pairs of states. f
0 1

0 1 g
ae ae bh c
1 0
bh 0
df 1 h
1 df g
0 a b c d e f g
27
 DFA Minimization: Example
0 1

0 1 0
a b c d
1 0 1
0 1
1 1 0
e f g h
1 0

5. Delete unreachable states: None

0 1

0 1
ae bh c
1 0
0
1
1 df g
0
28
?
29