Scribd
Upload
13 views2 pages

Equivalence and Minimization of Automata

This document describes how to minimize a finite state automata using the equivalence method in two steps. The first step is to identify all pairs of states (p,q) where p is not equal to q, and mark the pairs where exactly one state is final. The second step is then to group the states into equivalence classes, where each equivalence class represents a state in the minimized automata.

Uploaded by

Piyush Kulkarni
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views2 pages

Equivalence and Minimization of Automata

This document describes how to minimize a finite state automata using the equivalence method in two steps. The first step is to identify all pairs of states (p,q) where p is not equal to q, and mark the pairs where exactly one state is final. The second step is then to group the states into equivalence classes, where each equivalence class represents a state in the minimized automata.

Uploaded by

Piyush Kulkarni
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

7/27/2016

Minimize Automata

QXE

q0

q1

q0

q1

q0

q2

q2

q3

q1

q3

q3

q0

q4

q3

q5

q5

q6

q4

q6

q5

q6

q7

q6

q3

Cannot apply Rules of Replacement as now


two transitions match
Solution:
Equivalence Method
Two steps
1. Identify the pairs(p,q) such that p q
2. Identify equivalence classes

1. Identify the pairs(p,q) such that p q


Example - 1

(Marked pairs are


Distinguished
pairs)

List all pairs of states in given format

On the first pass, mark each pair of which


exactly one element if final state(i.e.
Distinguished state)
On each subsequent pass, mark any pair (p,q)
Iff (p,a) = r AND (q,a) = s && pair(r,s) is
already marked i.e.(r,s) are distinguishable
STOP after a pass in which no new pairs are
marked.

7/27/2016

Step 2 : Identify Equivalence Classes(EC)


First state of M corresponds to
first Equivalence Class
For each subsequent state q, q
represents new EC iff pair (p,q)
is marked
EC 1(P1)
EC 2(P2)
EC 3(P3)

1,2,4
3,5,7
6

You might also like