TOC : Minimization Of Finite Automata

Minimization of Finite Automata means minimize the number of states.

Merge those states which are equivalent.

When we say two states are equivalent ? when incoming edge from state a and b are meet at same state than we can say that a and b are equivalent.

(a,0) and (b,0) meet at state c so they are equivalent and represented as

But if we have 

then we say a is not equivalent to b

Note:  Minimization is only possible for DFA . NFA can not be minimized. 

There are two type of method for minimization:

1. Tabular method

2. Set method.

Let we understand both method by the help of example:

Tabular Method

Steps to apply tabular method:

Step 1: First draw a horizontal and vertical line. Write states below the horizontal line but one less than total like (a,b,c,d,e,f,,g) but ignore h.

Same way write states towards vertical line one less then total states. Here we start from (h,g,f,e,d,c,b) ignore state a.

Step 2: Make all the horizontal and vertical line in following manner such as 

            h to g , g to f , f to e , e to d , d to c , c to b , b to a .

Step 3: Mark (X) of all rows and column of final state.

Step 4: Trace all state with their input symbol.

Find which destination states are same:

Those states which are same , call as equivalent states such as : 

For complete method see below video:

Final Minimized Finite Automate will be:

Set method:

This method is also used for minimizing  finite automata.

Let we understand set method by the help of an example

Transition Diagram :

Transition table :

1. Construct two set one for final state and another for non final state. such as:

          Non Final State:  { a , b , c , e , f , g , h } 

                  Final State:  { d }

2.  Construct these set as a group and element of different group can not be merged.

         Group 1 :  { a , b , c , e , f , g , h } 

         Group 2 :  { d }

3. These group are combined by a group and labelled by Π₀ .

          Π₀  = (  { a , b , c , e , f , g , h }   { d } )

Note: We also call Pi Zero as Zero Equivalence.

We Have Zero Equivalence Now We Will Find One Equivalence Or Pi One. For finding One Equivalence we will use zero Equivalence.

First of all we will check a and b in  zero Equivalence and check from transition table on giving 0 and 1 input 

 

This means  if we give 0 input on state a than we get state b and on 1 input on state a we get state a.

In the same way if we give 0 input on state a than we get state b and on 1 input on state a we get state a.

Know see is b and a are in same set in 0 equivalence and also a and c are in same set .

Know see complete process or method  from below video.

Final minimized Finite Automata will be:

Practice Questions :

Construct a minimize state automation equivalent to the following  finite automata.

1.  

2. 

3.

4.