Minimization of Finite Automata
Minimization of Finite Automata
The term minimization refers to the construction of finite automata with a minimum number of states, which is equivalent to the given finite automata. The number of states used in finite automata directly depend upon the size of the automata that we have used. So, it is important to reduce the number of states. We minimize the finite automata by detecting those states of automata whose presence or absence does not affect the language accepted by the finite automata.
Some important concepts used in the minimization of finite automata
- Unreachable state
- Dead State
Unreachable state: Unreachable state is that state in which finite automata never reaches during the transition from one state to another state.
In the above DFA, we have unreachable state E, because on any input from the initial state, we are unable to reach to that state. This state is useless in finite automata. So, the best solution is to eliminate these types of states to minimize the finite automata.
Dead State: It is a non-accepting state, which goes itself for every possible input symbol.
In the above DFA, we have q5, and q6 are dead states because every possible input symbol goes to itself.
Minimization of Deterministic Finite Automata
The following steps are used to minimize a Deterministic Finite Automata.
Step1: First of all, we detect the unreachable state.
Step2: After detecting the unreachable state, in the second step, we eliminate the unreachable state (if found).
Step3: Identify the equivalent states and merge them.
- In this, we divide all the states into two groups:
- Group A: This group contains all accepting states of automata.
- Group B: This group contains all non-accepting states of automata.
This step is repeated for every group. Find group the input lead to if there are differences the partition the group into sets containing states which go to the same groups under the inputs.
- The resulting final partition contains equivalent states now merge them into a single state.
Step4: In this step, we detect dead states.
Step5: After detecting the dead states, the last step is to eliminate dead states.
Example:
Minimize the following DFA.
Solution
Step1: Detect unreachable states.
- Start form initial state. Add q0 to temporary state (T)
T = {q0}
- Now, for all states in temporary state set T, find transition from each state on each input symbol in ?. If resulting state is not in T add that state in T.
? (q0, a) = q1
? ( q0, b) = q2
Now, T = {q0, q1, q2}
Again
? ( q1, a) = q3
? ( q1, b) = q4
Now, T = {q0, q1, q2, q3, q4}
Again
? ( q2, a) = q3
? ( q2, b) = q5
Now, T = {q0, q1, q2, q3, q4, q5}
Again
? ( q3, a) = q3
? ( q3, b) = q1
Now, change in T because q1, q3 are already in set T.
T = {q0, q1, q2, q3, q4, q5}
Again
? ( q4, a) = q4
? ( q4, b) = q5
Now, change in T because q4, q5 are already in set T
T = {q0, q1, q2, q3, q4, q5}
Again
? ( q5, a) = q5
? ( q5, b) = q4
T = {q0, q1, q2, q3, q4, q5}
- Repeat previous step until T does not change
Finally we get T as:
T = {q0, q1, q2, q3, q4, q5}
- Now we will find unreachable states
U = Q – T
Q = {q0, q1, q2, q3, q4, q5, q6}
U = {q0, q1, q2, q3, q4, q5, q6} – {q0, q1, q2, q3, q4, q5}
U = {q6}, is the unreachable state
Step2: In this step, we eliminate the unreachable state found in first step.
Step3: Identify the equivalent steps and merge them.
- First of all, divide the states into two groups
Group A – q3, q4,q5 (contains accepting state)
Group B – q0, q1,q2 (contains non-accepting state)
Check Group A for input a
? (q3, a) = q3
? (q4, a) = q4
? (q5, a) = q5
In Similar way, check group A for input b
? (q3, b) = q1
? (q4, b) = q5
? (q5, b) = q4
q1 belongs to group B for input b, and q4 and q5 belong to group A for input b. So, we partition group A as:
Group A1 - q3
Group A2 – q4, q5
Group B – q0, q1, q2
Now, we check Group B – q0, q1, q2 for both input symbols
For input a, we have:
? (q0, a) = q1
? (q1, a) = q3
? (q2, a) = q3
For input b, we have
? (q0, b) = q2
? (q1, b) = q4
? (q2, b) = q5
q2 belongs to group B and q4, q4 belongs to group A2 for input b. So, we partition group B as:
Group B1 – q0
Group B2 – q1, q2
Check Group A2 for input a
? (q4, a) = q4 ? (q5, a) = q5
Check Group A2 for input b
? (q4, b) = q5 ? (q5, b) = q4
As both belong to the same group, the further division is not possible.
Now, we check Group B2 for input a and b
?(q1, a) = q3
?(q2, a) = q3
?(q1, b) = q4
?(q2, b) = q5
q4 and q5 belong to group A2 for input b. So no further partitioning is possible. Finally, the following groups are formed:
Group A1 – q3
Group A2 – q4, q5
Group B1 – q0
Group B2 – q1, q2
The resulting automata is given below:
Step4: In this step, we detected dead states. There are no dead states in the above DFA; hence it is minimized.