Scribd
Upload
35 views17 pages

Minimization

The document outlines the process of minimizing a Deterministic Finite Automaton (DFA) using the equivalence theorem, which involves eliminating dead and unreachable states, creating a state transition table, and partitioning states into equivalent sets. It provides a step-by-step guide to applying the theorem, including initializing sets, partitioning states, and merging equivalent states to form a minimal DFA. The document concludes with an example of minimizing a DFA and asks how many states remain after the minimization process.

Uploaded by

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

Minimization

The document outlines the process of minimizing a Deterministic Finite Automaton (DFA) using the equivalence theorem, which involves eliminating dead and unreachable states, creating a state transition table, and partitioning states into equivalent sets. It provides a step-by-step guide to applying the theorem, including initializing sets, partitioning states, and merging equivalent states to form a minimal DFA. The document concludes with an example of minimizing a DFA and asks how many states remain after the minimization process.

Uploaded by

theblack1257
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 17

DFA Minimization

• Productive states
• Non-productive states
• Dead state
• Unreachable state
• Equal state
Minimization of DFA Using Equivalence Theorem-

•Step 1:Eliminate all the dead states and


inaccessible states from the given DFA (if
any).
•Step 2: Draw a state transition table for the
given DFA.
All those states which can never be reached from the initial
state are called as inaccessible states.
All those non-final states which transit to itself for all input
symbols in ∑ are called as dead states.
• Step 3: Now, start applying equivalence theorem.

• Take a counter variable k and initialize it with value 0.


• Divide Q (set of states) into two sets such that one set
contains all the non-final states and other set contains
all the final states.
• This partition is called P0.
• Step-04:
•
• Increment k by 1.
• Find Pk by partitioning the different sets of P k-1 .
• In each set of Pk-1 , consider all the possible pair of states within
each set and if the two states are distinguishable, partition the
set into different sets in Pk.
• Step-05:
•
• Repeat step-04 until no change in partition occurs.
• In other words, when you find Pk = Pk-1, stop.
•
• Step-06:
•
• All those states which belong to the same set are equivalent.
• The equivalent states are merged to form a single state in the minimal
DFA.
• Number of states in Minimal DFA= Number of sets in P k
• Step 1: In the given DFA, q2 and q4 are the
unreachable states so remove them.
• Step 2: Draw the transition table for the rest of the
states.
State 0 1

→q0 q1 q3

q1 q0 q3

*q3 q5 q5

*q5 q5 q5
• Step 3: Now divide rows of transition table into two
sets as:
• 1. One set contains those rows, which start from non-
final states:
State 0 1

q0 q1 q3

q1 q0 q3
• Another set contains those rows, which starts from final
states.
State 0 1

q3 q5 q5

q5 q5 q5
• Step 4: Set 1 has no similar rows so set 1 will be the
same.
• Step 5: In set 2, row 1 and row 2 are similar since q3
and q5 transit to the same state on 0 and 1. So skip q5
and then replace q5 by
State 0 q3 in the rest.
1

q3 q3 q3
• Step 6: Now combine set 1 and set 2 as:

State 0 1

→q0 q1 q3

q1 q0 q3

*q3 q3 q3
Now it is the transition table of minimized DFA.
The minimum state automation equivalent to the
below FSA has how many number of states?
How many number of states
obtained after minimization?

You might also like