Minimization of DFA-
The process of reducing a given DFA to its minimal form is called as minimization of DFA. |
- It contains the minimum number of states.
- The DFA in its minimal form is called as a Minimal DFA.
How To Minimize DFA?
The two popular methods for minimizing a DFA are-
In this article, we will discuss Minimization of DFA Using Equivalence Theorem.
Minimization of DFA Using Equivalence Theorem-
Step-01:
- Eliminate all the dead states and inaccessible states from the given DFA (if any).
Dead State
All those non-final states which transit to itself for all input symbols in ∑ are called as dead states.
Inaccessible State
All those states which can never be reached from the initial state are called as inaccessible states. |
Step-02:
- Draw a state transition table for the given DFA.
- Transition table shows the transition of all states on all input symbols in Σ.
Step-03:
Now, start applying equivalence theorem.
- Take a counter variable k and initialize it with value 0.
- Divide Q (set of states) into two sets such that one set contains all the non-final states and other set contains all the final states.
- This partition is called P_{0}.
Step-04:
- Increment k by 1.
- Find P_{k} by partitioning the different sets of P_{k-1} .
- In each set of P_{k-1} , consider all the possible pair of states within each set and if the two states are distinguishable, partition the set into different sets in P_{k}.
Two states q_{1} and q_{2} are distinguishable in partition P_{k} for any input symbol ‘a’,
if δ (q_{1}, a) and δ (q_{2}, a) are in different sets in partition P_{k-1}. |
Step-05:
- Repeat step-04 until no change in partition occurs.
- In other words, when you find P_{k} = P_{k-1}, stop.
Step-06:
- All those states which belong to the same set are equivalent.
- The equivalent states are merged to form a single state in the minimal DFA.
Number of states in Minimal DFA
= Number of sets in P_{k} |
PRACTICE PROBLEMS BASED ON MINIMIZATION OF DFA-
Problem-01:
Minimize the given DFA-
Solution-
Step-01:
The given DFA contains no dead states and inaccessible states.
Step-02:
Draw a state transition table-
a | b | |
→q0 | q1 | q2 |
q1 | q1 | q3 |
q2 | q1 | q2 |
q3 | q1 | *q4 |
*q4 | q1 | q2 |
Step-03:
Now using Equivalence Theorem, we have-
P_{0} = { q_{0} , q_{1} , q_{2} , q_{3} } { q_{4} }
P_{1} = { q_{0} , q_{1} , q_{2} } { q_{3} } { q_{4} }
P_{2} = { q_{0} , q_{2} } { q_{1} } { q_{3} } { q_{4} }
P_{3} = { q_{0} , q_{2} } { q_{1} } { q_{3} } { q_{4} }
Since P_{3} = P_{2}, so we stop.
From P_{3}, we infer that states q_{0} and q_{2} are equivalent and can be merged together.
So, Our minimal DFA is-
Problem-02:
Minimize the given DFA-
Solution-
Step-01:
- State q_{3} is inaccessible from the initial state.
- So, we eliminate it and its associated edges from the DFA.
The resulting DFA is-
Step-02:
Draw a state transition table-
a | b | |
→q0 | *q1 | q0 |
*q1 | *q2 | *q1 |
*q2 | *q1 | *q2 |
Step-03:
Now using Equivalence Theorem, we have-
P_{0} = { q_{0} } { q_{1} , q_{2} }
P_{1} = { q_{0} } { q_{1} , q_{2} }
Since P_{1} = P_{0}, so we stop.
From P_{1}, we infer that states q_{1} and q_{2} are equivalent and can be merged together.
So, Our minimal DFA is-
Problem-03:
Minimize the given DFA-
Solution-
Step-01:
The given DFA contains no dead states and inaccessible states.
Step-02:
Draw a state transition table-
0 | 1 | |
→q0 | q1 | q3 |
q1 | q2 | *q4 |
q2 | q1 | *q4 |
q3 | q2 | *q4 |
*q4 | *q4 | *q4 |
Step-03:
Now using Equivalence Theorem, we have-
P_{0} = { q_{0} , q_{1} , q_{2} , q_{3} } { q_{4} }
P_{1} = { q_{0} } { q_{1} , q_{2} , q_{3} } { q_{4} }
P_{2} = { q_{0} } { q_{1} , q_{2} , q_{3} } { q_{4} }
Since P_{2} = P_{1}, so we stop.
From P_{2}, we infer that states q_{1} , q_{2} and q_{3} are equivalent and can be merged together.
So, Our minimal DFA is-
Problem-04:
Minimize the given DFA-
Solution-
Step-01:
- State q_{5} is inaccessible from the initial state.
- So, we eliminate it and its associated edges from the DFA.
The resulting DFA is-
Step-02:
Draw a state transition table-
0 | 1 | |
→q0 | q1 | q2 |
q1 | q2 | *q3 |
q2 | q2 | *q4 |
*q3 | *q3 | *q3 |
*q4 | *q4 | *q4 |
Step-03:
Now using Equivalence Theorem, we have-
P_{0} = { q_{0} , q_{1} , q_{2} } { q_{3} , q_{4} }
P_{1} = { q_{0} } { q_{1} , q_{2} } { q_{3} , q_{4} }
P_{2} = { q_{0} } { q_{1} , q_{2} } { q_{3} , q_{4} }
Since P_{2} = P_{1}, so we stop.
From P_{2}, we infer-
- States q_{1} and q_{2} are equivalent and can be merged together.
- States q_{3} and q_{4} are equivalent and can be merged together.
So, Our minimal DFA is-
Also Read- Construction of DFA
To gain better understanding about Minimization of DFA,
Next Article- Converting DFA to Regular Expression
Get more notes and other study material of Theory of Automata and Computation.
Watch video lectures by visiting our YouTube channel LearnVidFun.