Minimization of DFA | Steps to minimize the DFA
MINIMISATION OF DFA is the procedure through which we can obtain minimized DFA which consists of a minimum number of states.
There are two classes of states that can be removed or merged from the original DFA without affecting the language it accepts to minimize it.
- Unreachable states are the states that are not reachable from the initial state of the DFA, for any input string.
- Nondistinguishable states are those that cannot be distinguished from one another for any input string.
Let p and q be two states then (p,q) are equivalent states and this two states in a DFA can be replaced by a single state if where state p on seeing input a goes to final state implies that state q also goes to the final state.
STEPS TO MINIMIZE DFA:
- Remove the unreachable states from DFA.
- Draw the transition table for the remaining states.
- Now, divide rows of transition table in 2 states as Set-1 consists of all the non-final states and Set-2 contains final states.
- Search for similar rows(for different sets deriving output states are same on same input symbol)
- Merge them and repeat the procedure for the rest of the table.
- Draw the transition diagram for minimized DFA.
EXAMPLE:
Step-I: Delete a state which is unreachable from the initial state. In this problem, there is no dead state, therefore, proceed to next step.
Step-II: Draw the transition table.
|
a |
b |
q0 |
q1 |
q2 |
q1 |
q1
|
q3 |
q2 |
q1 |
q2 |
q3 |
q1 |
q4 |
q4 |
q1 |
q2 |
Step-III: Try to find out equivalent sets(sets of all non final states and final states)
- [q0, q1,q2,q3][q4] (separating final and non-final states into different sets)
- [q0q2][q1,q3][q4] (q0 and q2 equivalent states)
- [q0q2][q1][q3][q4] (q1 and q3 will be in different set as they are not equivalent)
Newly formed states after minimizing the DFA are q0q2, q1, q3, q4.
Step-IV: Draw the minimized DFA.