Minimization of Deterministic Finite Automata

Minimization of Deterministic Finite Automata:

Minimization of automata refers to detect those states of automata whose presence or absence in a automata does not affect the language accepted by automata. these states are like Unreachable states, Dead states, Non-distinguishable states etc.

Example:

Consider the following transition table example :

State	0	1
-> q0	q1	q5
q1	q6	q2
q2 (Final state)	q0	q2
q3	q2	q6
q4	q7	q5
q5	q2	q6
q6	q6	q4
q7	q6	q2

Minimize the above finite automata.

Solution:

For minimizing the above automata, we will have to make п  (pi) sets.

пo = { {q2}, {q0, q1, q3,q4,q5,q6,q7}}

п1 = { {q2}, {q0, q4,q6}, {q1,q7}, {q3,q5}}

п2 = { {q2}, {q0, q4}, {q6}, {q1,q7}, {q3,q5}}

п3 = { {q2}, {q0, q4}, {q6}, {q1,q7}, {q3,q5}}

here п2 = п3  so stop making п sets.

[Trick: for making п  sets, first of all make пo set.  for this, make two set, first set contains final state and second set contains non final states.

For п1 set , there are two sets in пo:

     First set =  {q2}, that can not be partitioned further.

     Second set = {q0, q1, q3,q4,q5,q6,q7}, that can be partitioned.

For partitioned second set, consider q0 and q1, the entries corresponding to q0 and q1under 0-column are q1 and q6. these entries belongs to second set.so no problem.

the entries corresponding to q0 and q1under 1-column are q5 and q2. in this q2 entry belongs to first set and q5 belong to second set. so problem occur.

due to this, we can not make combination of q0 and q1.

similarly check (q0,q3), {q0,q4), (q0,q5), (q0, q6), (q0,q7) states.

after checking all the states with q0, we make a new set {q0, q4, q6}.

after making new set, the remaining states are {q1,q3,q5,q7}.

Now we check states (q1,q3), (q1,q5), (q1,q7) states by following above procedure. after this, we get a new set {q1, q7}. and remaining states are {q3, q5}.

finally we check states (q3, q5) by following above procedure.

after checking all this, we make new set п2,

п2 = { {q2}, {q0, q4}, {q6}, {q1,q7}, {q3,q5}}

similar procedure applied to п2 set.

then we get п3 set. we make п sets until we find last two п sets equal.

in this example, we find  п2 = п3  so stop making п sets.

Final minimized DFA table is : 

State	0	1
[q0, q4]	[q1, q7]	[q3, q5]
[q1, q7]	[q6]	[q2]
[q2]	[q0, q4]	[q2]
[q3, q5]	[q2]	[q6]
[q6]	[q6]	[q0, q4]

we take states from п3 set in minimized DFA table. after making minimized DFA table, we can make finite automata.

   Exercises:

1. Construct the minimum state automaton equivalent to the following transition table:

State	a	b
-> q0	q1	q0
q1	q0	q2
q2	q3	q1
q3 (Final state)	q3	q0
q4	q3	q5
q5	q6	q4
q6	q5	q6
q7	q6	q3

                

2. Construct the minimum state automaton equivalent to the following transition table:

State	0	1
-> q0	q0	q3
q1	q2	q5
q2	q3	q4
q3 (Final state)	q0	q5
q4	q0	q6
q5	q1	q4