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:
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
![Optimization of DFA](https://static.javatpoint.com/compiler/images/optimization-of-dfa.png)
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.
![Optimization of DFA 1](https://static.javatpoint.com/compiler/images/optimization-of-dfa1.png)
Step 3:
Now divide rows of transition table into two sets as:
1. One set contains those rows, which start from non-final sates:
![Optimization of DFA 2](https://static.javatpoint.com/compiler/images/optimization-of-dfa2.png)
2. Other set contains those rows, which starts from final states.
![Optimization of DFA 3](https://static.javatpoint.com/compiler/images/optimization-of-dfa3.png)
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.
![Optimization of DFA 4](https://static.javatpoint.com/compiler/images/optimization-of-dfa4.png)
Step 6: Now combine set 1 and set 2 as:
![Optimization of DFA 5](https://static.javatpoint.com/compiler/images/optimization-of-dfa5.png)
Now it is the transition table of minimized DFA.
Transition diagram of minimized DFA:
![Optimization of DFA 6](https://static.javatpoint.com/compiler/images/optimization-of-dfa6.png)
Fig: Minimized DFA
0 Comments