Reputation: 131
So this is the DFA in the question needs to be minimzed
The answer to this question is this and as you can see the DFA is minimized now.
My question is : as you can see the minimized DFA has a state q7 which is unreachable from the start or initial state. So why they are showing state q7 in the final answer, shouldn't the unreachable state be removed to make this dfa even more minimized.
Upvotes: 1
Views: 3715
Reputation: 26
If you look carefully none of the states q4,q5,q6,q7 are reachable from the initial state q0, not just q7, so all these 4 states should be removed. my solution for this would start from q0,q1,q2,q3, and then follow the procedure of reduction.
This is what I think the answer should be:
Upvotes: 1
Reputation: 28292
Let's be practical for a moment. Definitions and constructions aside, a minimal DFA corresponding to the given DFA should be a DFA which accepts the same language and has as few states as possible. Any other definition of DFA minimization is not as useful as this one. Given this, the answer to your questions is unambiguously that q7 MUST NOT be in the minimized DFA, since a DFA without q7 accepts the same language and has fewer states. We can argue about whether a particular minimization procedure would remove it or whatever ad infinitum, but really that state must go. Another reason it must go is that the Myhill-Nerode theorem tells us a minimal DFA for this language must have the same number of states in a minimal DFA for this language as we do equivalence classes over the indistinguishability relation. Because no string leads to q7, there is no equivalence class for it at all, and there certainly can't be a new one it adds.
TL;DR - q7 is not a state in a minimal DFA corresponding to the given DFA. Make of that what you will.
Upvotes: 0