To optimize the DFA you have to follow the various steps. These are as follows:
Step 1: Remove all the states that are unreachable from the initial state via any set of the transition of DFA.
Step 2: Draw the transition table for all pair of states.
Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states and T2 contains non-final states.
Step 4: Find the similar rows from T1 such that:
δ (q, a) = p
δ (r, a) = p
That means, find the two states which have same value of a and b and remove one of them.
Step 5: Repeat step 3 until there is no similar rows are available in the transition table T1.
Step 6: Repeat step 3 and step 4 for table T2 also.
Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the transition table of minimized DFA.
Example
Solution:
Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them.
Step 2: Draw the transition table for rest of the states.
Step 3:
Now divide rows of transition table into two sets as:
1. One set contains those rows, which start from non-final sates:
2. Other set contains those rows, which starts from final states.
Step 4: Set 1 has no similar rows so set 1 will be the same.
Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to same state on 0 and 1. So skip q5 and then replace q5 by q3 in the rest.
Step 6: Now combine set 1 and set 2 as:
Now it is the transition table of minimized DFA.
Transition diagram of minimized DFA:
Fig: Minimized DFA
0 Comments