Finite Automata

Minimization of DFA



One important result on finite automata, both theoretically and practically, is that for any regular language there is a unique DFA having the smallest number of states that accepts it. Let M = < Q , , q0 , , A > be a DFA that accepts a language L. Then the following algorithm produces the DFA, denote it by M1, that has the smallest number of states amomg the DFAs that accept L.

Minimization Algorithm for DFA

Construct a partition = { A, Q - A } of the set of states Q ;
new := new_partition(} ;
while (new )
        := new ;
        new := new_partition()
final := ;


function new_partition()
for each set S of do
        partition S into subsets such that two states p and q of S are in the same subset of S
        if and only if for each input symbol, p and q make a transition to (states of) the same set of .

        The subsets thus formed are sets of the output partition in place of S.
        If S is not partitioned in this process, S remains in the output partition.
end


Minimum DFA M1 is constructed from final as follows:

Remove from M1 the dead states and the states not reachable from the start state, if there are any. Any transitions to a dead state become undefined.
A state is a dead state if it is not an accepting state and has no out-going transitions except to itself.


Example 1 :
Let us try to minimize the number of states of the following DFA.


   




Initially = { { 1 , 5 } , { 2 , 3 , 4 } }.

new_partition is applied to .
Since on b state 2 goes to state 1, state 3 goes to state 4 and 1 and 4 are in different sets in , states 2 and 3 are going to be separated from each other in new .
Also since on a sate 4 goes to sate 4, state 3 goes to state 5 and 4 and 5 are in different sets in , states 3 and 4 are going to be separated from each other in new.
Further, since on b 2 goes to 1, 4 goes to 4 and 1 and 4 are in different sets in , 2 and 4 are separated from each other in new.
On the other hand 1 and 5 make the same transitions. So they are not going to be split.

Thus the new partition is { { 1 , 5 } , { 2 } , { 3 } , { 4 ] }. This becomes the in the second iteration.

When new_partition is applied to this new , since 1 and 5 do the same transitions, remains unchanged.
Thus final = { { 1 , 5 } , { 2 } , { 3 } , { 4 ] }.

Select 1 as the representative for { 1 , 5 }. Since the rest are singletons, they have the obvious representatives.
Note here that state 4 is a dead state because the only transitionout of it is to itself.
Thus the set of states for the minimized DFA is { 1 , 2 , 3 }.
For the transitions, since 1 goes to 3 on a, and to 2 on b in the original DFA, in the minimized DFA transitions are added from 1 to 3 on a, and 1 to 2 on b. Also since 2 goes to 1 on b, and 3 goes to 1 on a in the original DFA, in the minimized DFA transitions are added from 2 to 1 on b, and from 3 to 1 on a.
Since the rest of the states are singletons, all transitions between them are inherited for the minimized DFA.

Thus the minimized DFA is as given in the following figure:



   






Example 2 :
Let us try to minimize the number of states of the following DFA.


   




Initially = { { 3 } , { 1 , 2 , 4 , 5 , 6 } }.
By applying new_partition to this , new = { { 3 } , { 1 , 4 , 5 } , { 2 , 6 } } is obtained.
Applyting new_partition to this , new = { { 3 } , { 1 , 4 } , { 5 } , { 2 } , { 6 } } is obtained.
Applyting new_partition again, new = { { 1 } , { 2 } , { 3 } , { 4 } , { 5 } , { 6 } } is obtained.
Thus the number of states of the given DFA is already minimum and it can not be reduced any further.


Test Your Understanding of Minimization of DFA

Indicate which of the following statements are correct and which are not.
Click True or Fals , then Submit.












Next -- Application of FA

Back to Study Schedule

Back to Table of Contents