Minimal of DFA
Minimal of DFA uses the minimum number of states needed to represent a language. It means that if you remove a single state than whole Minimal of DFA is effect. Minimal of DFA or MFA are also known as Minimization of DFA.
| Note: MFA is always unique for a language. |
It is difficult to design a directly minimal of DFA so, we design first the DFA and then minimize it.
According to a based on productivity, the states of DFA can be divided in two types. So, two types of states of DFA are as follow.
Types of States of DFA
i) Productive States
ii) Non-Productive States
The Explanation of types of two states of DFA are as given.
i) Productive States
A state is called Productive States that, if removed a state from the machine, will affect its ability to accept the language is known as Productive States.
ii) Non-Productive States
A state is called Non-Productive States that, if removed a state from the machine, will not affect its ability to accept the language is known as Non-Productive States. Non-Productive States is more important than Productive States. They can be a divided into three parts.
- Dead State
- Unreachable State
- Equal State
i) Dead State
A state from which there is no way to reach the final state is known as dead state. It is also known as Non-Productive State. Even it is a non-productive, we do not remove it during minimization because it completes the system. If there is more than one dead state, we merge them into a single dead state. Dead State can be merged during DFA minimization.
Example
Explanation
At State q0
- For Input b: Transition goes to q1.
- For Input a: Transition goes to q3.
- For Input c: Transition goes to q3.
At State q1
- For Input c: Transition goes to q2.
- For Input a: Transition goes to q3.
- For Input b: Transition goes to q3.
At State q2
- For Input a: Transition goes to q3.
- For Input b: Transition goes to q3.
- For Input c: Transition goes to q3.
At State q3
- For Input a: Transition goes to q3.
- For Input b: Transition goes to q3.
- For Input c: Transition goes to q3.
Explanation
Hence the more explanation are as given.
- States = {q0,q1,q2,q3}
- Input Alphabet = {a,b,c}
- Initial State = q0
- Final State = q2
- Dead State = q3
So, Transition Table are also given.
| Note: q3 is a dead state. |
ii) Unreachable State
Unreachable state is the state where we cannot reach is known as Unreachable State. Unreachable State is also known as Non-Productive States. In Unreachable State starting from the initial state and than we process the input string. We can remove the unreachable state because we cannot reach this state. Unreachable State cannot be merged during DFA minimization.
Example
Explanation
It is Unreachable State because it did not have a dead state.
iii) Equal State
Two states are called equal state if they behave or act the same for every input string. In more simple words we can say that, if two states give the same result (Final or Non-Final) for every input string, they are called equal state. Equal State are also known as Non-Productive State. Equal State can be merged during DFA minimization.
Example
Explanation
Therefore, q0 and q1 are the equal states and can be merged into one state during DFA minimization.