Minimization of DFA Solved example using Equivalence method in automata

Minimization of DFA examples using Partition Method or Equivalence Theorem:

Minimization of DFA means reduction of states.If X & Y are two states in a DFA, we can combine these two states into single state {X,Y} if they are not distinguishable i.e. equivalent or indistinguishable. Two states are said to be indistinguishable or equivalent state if δ (X, w) and δ (Y, w) are going to accepting /final states or going to non-accepting /non-final states.It is also called as State minimization.
Symbolically this can be represented as
1.      δ (X, w)  ∈ F and δ (Y, w) ∈ F
                       OR
2.      δ (X, w)  ∉ F and δ (Y, w) ∉ F

Minimization of DFA steps/rules of minimization of DFA in automata:

Minimization of DFA questions or  problems using partition method  can be solved by following steps(How to do minimization of DFA):
Step1: Try to delete all the states to which we cannot reach from initial state (unreachable state)
Step2: Draw state transition table
Step3: Find out equivalent set
Step4: Draw / Construct minimized DFA
Note:
0-Equivalent Set: Try to separate non-final states from final states.
n-Equivalent Set: We take information only from previous equivalent set i.e.(n-1)-Equivalent
Set i.e. We will check, on seeing input symbol, are they going to same state or different state.
After checking if they are in same state group in previous equivalent set, then write in same group, otherwise make separate group. Follow this procedure until we get a point where we find “No change” in the state group.

Minimization of DFA Examples:


Example-2: Minimize the given DFA using partition method or construct minimized DFA using Equivalence method
Minimization of DFA Example
Given DFA

Solution:

Step-1: Try to delete all the states to which we cannot reach from initial state
Minimization of DFA Example
DFA without unreachable state
Step-2: Draw state transition table of DFA:

Present State
Next State
Input a
Input b
   à Q0
Q1
Q5
Q1
Q6
*Q2
*Q2
Q0
*Q2
Q4
Q7
Q5
        Q5
*Q2
Q6
Q6
Q6
Q4
Q7
Q6
*Q2


Step-3: Find out equivalent sets:

0-Equivalent Set: [Q0, Q1, Q4, Q5 , Q6, Q7] [Q2]
1-Equivalent Set: [ Q0, Q4, Q6] [Q1, Q7] [Q5] [Q2]
2-Equivalent Set: [Q0, Q4] [Q6] [Q1, Q7] [Q5] [Q2]
3-Equivalent Set: [Q0, Q4] [Q6] [Q1, Q7] [Q5] [Q2]

Step-4: Draw minimized DFA:


Minimized DFA

Minimization of DFA Examples:





Minimization of DFA Example-4

Minimization of DFA Example-5



Comments

Search related post on google