Minimization of Finite Automata
Prof. (Dr.) K.R. Chowdhary
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

kr chowdhary

TOC

1/ 14

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Introduction

Each DFA defines a unique
language but reverse is not
true.
Larger number of states in FA
require higher memory and
computing power.
An NFA of n states result to
2n maximum number of states
in an equivalent DFA,
therefore design of DFA is
crucial.

kr chowdhary

Minimization of a DFA refers
to detecting those states
whose absence does not affect
the language acceptability of
DFA.
A reduced Automata
consumes lesser memory, and
complexity of implementation
is reduced. This results to
faster execution time, easier to
analyze.

TOC

2/ 14

Some definitions
Unreachable states: If there
does not exist any q ′ , such
that δ ∗ (q0 , w ) = q ′ , then q ′ is
unreachable/unaccessible
state.

their behavior are
indistinguishable with respect
to each other. For example,
p, q are indistinguishable if
δ ∗ (p, w ) = δ ∗ (q, w ) = r ∈ Q
for all w ∈ Σ∗ .

Dead state: ∀a, a ∈ Σ, q is
dead state if δ (q, a) = q and
q ∈ Q −F.

k-equivalence: p, q are
k−equivalence if:
δ ∗ (q, w ) ∈ F ⇔ δ ∗ (p, w ) ∈ F ,

Reachability: FA M is
accessible if ∃w , w ∈ Σ∗ , and
(q0 , w ) ⊢∗ (q, ε) for all q ∈ Q.
⊢∗ is called reachability
relation.

for all w ∈ Σ∗ and |w | ≤ k;
written as p ∼k q.
If they are equivalent for all k,
then p ∼ k. The p ∼ q and
p ∼k q are equivalent
relations.

Indistinguishable states: Two
states are indistinguishable if

kr chowdhary

TOC

3/ 14

Minimization Example
and the state which remains
will have in addition, all
incoming transitions from the
removed state.
Similarly, the states q0 , q4 are
also indistinguishable states,
hence they can also be
merged. q3 is dead state.

q6 has no role, hence it can be
removed.
q1 , q5 are indistinguishable
states because their behavior
is identical for any string
supplied at these states.
These are called equivalent
states, and can be merged.
In merging of two equivalent
states, one state is eliminated,

kr chowdhary

TOC

4/ 14

Formalism for minimization
1

Identify and remove all
unreachable states: find all
reachable states R, the
non-reachable states are
Q − R.

3

Identify and merge of dead
states.

4

A sequence w is accepted if
δ ∗ (q, w ) ∈ F

Indistinguishability is an
equivalence relation. Let p, q, r
R = {q0 }
∈ Q. Let p ≡ q, if they are
while ∃p, p ∈ R ∧ ∃a, a ∈ Σ, indistinguishable. So,
and δ (p, a) ∈
/R
p ≡ p; reflexive
{

p ≡ q ⇔ q ≡ p; symmetry

R = R ∪ δ (p, a)

p ≡ q, q ≡ r ⇒ p ≡ r ;
transitivity, ∴,
indistinguishablity is an
equivalence relation.

}
2

Identify and merge of
indistinguishable states.

kr chowdhary

TOC

5/ 14

Formalism for minimization

Let x, y ∈ Σ∗ , then x and y
are said to be equivalent with
respect to L (i.e. x ≈L y ), if
for some z ∈ Σ∗ , xy ∈ L iff
yz ∈ L.
≈L relation is reflexive,
symmetric, and transitive, ∴,
it is equivalence relation,
which divides the language set

kr chowdhary

L into equivalence classes.
For a DFA M; x, y ∈ Σ∗ are
equivalent with respect to M,
if x, y both drive M from a
state q0 to same state q ′ ,
δ ∗ (q0 , x) = q ′ and
δ ∗ (q0 , y ) = q ′ ,
∴, x ≈M y

TOC

6/ 14

Minimization Example#1

(1)

There is no unreachable state

(2)

Indistinguishable states
q1 , q2 are indistinguishable, and q0 , q3 are distinguishable

(3)

Reduced automata: The set of distinguishable states are:
[s0 ] = {q0 }, [s1 ] = {q1 , q2 }, [s2 ] = {q3 }.
Start and final states are [s0 ], [s2 ].
kr chowdhary

TOC

7/ 14

Minimization Algorithm

The minimization algorithm is based on the following theorem:
Theorem
Let δ (p, a) = p ′ and δ (q, a) = q ′ , for a ∈ Σ. If p ′ , q ′ are distinguishable
then so are p, q.
Proof.
If p ′ , q ′ are distinguishable by wa then p, q are distinguishable by string
w.

kr chowdhary

TOC

8/ 14

Minimization Algorithm(Table Filling Algorithm)

1

Remove inaccessible/unreachable states:
delete Q − QR , where QR is set of accessible states.

2

Marking distinguishable states:
- Mark p, q as distinguishable, where p ∈ F , q ∈
/F
- For all marked pairs p, q and a ∈ Σ, if δ (p, a), δ (q, a) is already
marked distinguishable then mark p, q as distinguishable.

3

Construct reduced automata:
- Let the set of indistinguishable(equivalent) states be sets [pi ], [qj ], . . .
such that ∀i, j [pi ] ∩ [qj ] = φ and [pi ] ∪ [qj ] ∪ · · · = QR .
- For each δ (pi , a) = qj , add an edge from [pi ] to [qj ]

4

Mark the start and final states:
- if q0 ∈ [pi ] then mark [pi ] as start state,
- if qf ∈ F , then mark [qf ] as final state.

kr chowdhary

TOC

9/ 14

Implementation of Table Filling Algorithm

Steps:
1

Let M = (Q, Σ, δ , s, F ). Remove all the non-reachable states.

2

For p ∈ F and q ∈ Q − F , put “x” in table at (p, q). This shows that
p, q are distinguishable.

3

4

If ∃w , such that δ ∗ (p, w ) ∈ F and δ ∗ (q, w ) ∈
/ F , mark (p, q) as
distinguishable.
Recursion rule: if δ ∗ (p, w ) = r , δ ∗ (q, w ) = s, and (r , s) were earlier
proved distinguishable, then mark (p, q) also distinguishable in the
table.

kr chowdhary

TOC

10/ 14

Example: Table Filling algorithm to minimize a FA

Consider that we want to minimize the FA shown above. The state
q3 is unreachable, so it can be dropped.
Next, we mark the distinguishable states at begin as final and
non-final states. and make their entries in table as
(q2 , q0 ), (q2 , q1 ), (q4 , q2 ), (q5 , q2 ), (q6 , q2 ), (q7 , q2 ) and indicate these
by mark “x.”

kr chowdhary

TOC

11/ 14

Example: Table Filling algorithm to minimize a FA ...

Next we consider the case δ (q0 , 1) = q5 , δ (q1 , 1) = q2 . Since (q5 , q2 )
are already marked distinguishable, therefore, (q0 , q1 ) are also
distinguishable.
Like this we have filled the table shown above. The unmarked are
indistinguishable states.
kr chowdhary

TOC

12/ 14

Example: Table Filling algorithm to minimize a FA...

Only states pairs which are not marked distinguishable are {q0 , q4 }
and {q1 , q7 }. The automata shown in figure above is reduced
automata.

kr chowdhary

TOC

13/ 14

Bibliography

Chowdhary, K.R. (2025). Minimization of Finite Automata. In:
Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_4

kr chowdhary

TOC

14/ 14