prepare automata for GATE

 

Minimization of DFA is a highly important topic from GATE perspective. This article will provide a brief outline of the Minimization process, Steps required to Minimize the Automata and also describe solved examples.

  In order to assist you in your GATE preparation , We provide daily Free Quiz (chapter wise) , study tips , preparation Tips for GATE 2017 preparation .

Expert Tips and Tutorials to crack GATE 2018 Exam.

Subscribe Here     

You can subscribe and get daily FREE Quiz (Chapter Wise) , study tutorials  and tips delivered on your personal email id  to crack the upcoming GATE Exam.

What is Minimization?

Minimization is defined as the process of transforming a given deterministic finite automaton (DFA) into an equivalent DFA with minimum number of states.

What is the Need for Minimization?

It is essential to minimize a DFA before its implementation. Minimization is done in order to save space taken up by redundant states and transitions.

Minimization helps in removal of non-reachable states, trap states and the indistinguishable states.

Steps for Minimization of DFA

  1. First of all, identify and remove the unreachable states. Unreachable states are the ones which have no incoming transition but only have an outgoing transition.

 important article : Most Important Topics For GATE-2017 (CSE) || guaranteed Results

  

      2. (p,q) are two states and they are equivalent if the following conditions are satisfied:

                δ(p,w) ε F which implies that a state p after undergoing transition on input string w gives a state belonging to set of final states F and δ (q,w) ε F which implies that a state q after undergoing transition on input string w gives a state which belongs to Set of Final States F.

 

     3. Find 0-equivalent

               Separate the non-final states from the final states

When Mod (w) = 0, then (p,q) are 0-equivalent

 

 must read : 6 Month Study Plan/TimeTable To Crack GATE (CS) 2017 By Experts

     4. Find 1-Equivalent

In this, we take a pair of initial and each corresponding state in the set of non-final states and check whether they are equivalent or not.We place the equivalent states in one set and place all non-equivalent states in different sets.

 

     5. Find 2-Equivalent

From the set obtained in 1-Equivalent, proceed by checking the states belonging to the same set.The process of finding equivalents continues till we obtain the minimized DFA.

 

FREE Simulation Mock Test for BSNL-JE.

Start Test  

Solved Examples on Minimization of DFA

  1. Find the minimized DFA for the figure shown below:

               

 

Soln:  In this question, q0 is the initial state and q4 is the final state.

 

Step 1 : First, draw the transition table. Next, we need to remove the unreachable or inaccessible states.

 

 

State

Transition Function

 

a

b

q0

q1

q2

q1

q1

q3

q2

q1

q2

q3

q1

q4

q4

q1

q2

               

  Step 2  : Find 0- Equivalent set. In this, we need to separate the non-final states from the final states.

                [ q0 q1 q2 q3 ] [q4]

  Step 3 : Find the 1-Equivalent set. First, we consider [q0 q1].(q0 q1) go to state q1 after transition on a and go to states q2 and q3 after transition on b. Since q2 and q3 belong to the same set of final states, therefore, [ q0 q1 ] are equivalent.

                Next, take [q0 q2].(q0 q2) go to q1 after transition on a and q2 after transition on b.

Therefore, [q0 q2] are also equivalent.

                 Next, take [q0 q3] . (q0 q3) go to q1 after transition on a and q2 and q4 are transition on b. Therefore, [q0 q3] are not equivalent since q2 and q4 belong to the different set of final states.

 Therefore, the 1-equivalent will consist of:    [q0, q1, q2]  [q3]  [q4]

must read : Experts Tips to Solve NP-Complete Problems in GATE 2017

Step 4  : Find the 2-Equivalent .First, we check [q0 q1]. (q0 q1) go to q1 after transition on a and go to q2 and q3 after transition on b.

Since, q2 and q3 belong to the different set of final states, Therefore, [q0 q1] are not equivalent. Next, we check [q0 q2].

(q0 q2) go to q1 after transition on a and q2 after transition on b. Therefore, [q0 q2] are equivalent.

 Therefore, 2-equivalent would be [q0 ,q2] [q1] [q3] [q4] .

 

Step 5 :

Finding further equivalent would result in the same set of states. Therefore, the minimized DFA would be

In this, [q0 q2] would be taken as a single state since these two are equivalent. Finally, we obtain the following minimized DFA.

 

Best Wishes !!

FREE Simulation Mock Test for BSNL-JE.

Start Test  

 

Search on PrepLadder