# Minimizing DFA - Dead state elimination

Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, should be eliminated right?

UPDATE: My solution to the question in the comment

• The "dead state" cannot be eliminated because we need to fill in a transition from $q$ on $b$. If we don't put in a dead state, like the last option, it will accept the string "bba" while the original DFA doesn't. The other option B can be eliminated as it doesn't accept "ba" while the original one does. – Gokul Nov 9 '18 at 7:59
• This DFA accepts all languages (over $\{a,b\}$ alphabet) except $bb\{a, b\}^*$. So, you can't get rid of $r$. If $r$ was an dead state too, then the minimal DFA would be one-state. – rus9384 Nov 9 '18 at 11:19
• @rus9384 okay...thanks . Is the elimination of the dead state mentioned in this problem correct . ibb.co/iav4QA – techno Nov 9 '18 at 17:16
• A is correct, D is not, D accepts all languages except $b^*$. It is not minimal either, $p$ and $q$ can be merged in one state. – rus9384 Nov 9 '18 at 17:21
• @rus9384 why? 1 and 5 can be combined into a single state as they have identical transitions . – techno Nov 13 '18 at 9:59

## 2 Answers

The given dfa (d) will be formed. As far as your question about removal of state r: it can't be removed because state q is having transition to state r on input b. This is necessary because a dfa cannot leave any input transition, that is, it must define all the transitions for each and every state and for each and every input given to those states.

• Thanks a lot for solving the question.But if you cannot eliminate dead state with moves to it why is 4 eliminated here ibb.co/iav4QA – techno Nov 9 '18 at 9:59
• @techno in the link that you provided, the answer in the option in (b) don't even seems like a dfa to me. The states 3 and 2 don't have transitions defined for inputs b and a respectively. – Shubham Singh Manhas Nov 10 '18 at 14:11
• hmm strange its from GATE 2019 book by Pearson.. – techno Nov 13 '18 at 10:00
• Please see the update... is this a correct solution to the question in the comment. – techno Nov 13 '18 at 10:06
• @techno it seems correct to me, state 4 is the trap state and any input thereafter will be trapped in it. – Shubham Singh Manhas Nov 14 '18 at 11:43

There are two ways to define DFAs. In the more common way, for each state $$q$$ and symbol $$\sigma$$ there is exactly one edge exiting $$q$$ and labeled $$\sigma$$. In the lest common way, there is at most one such edge.

If you are using the second convention, then you are right that the dead state is not needed. But when using the first convention, dead states are necessary. Indeed, what should the automaton do upon reading $$bb$$? Any word starting $$bb$$ should be rejected, but the automaton has to reach some state upon reading $$bb$$; this is the dead state.

• So... is the answer right? Please see my comment for the answer above... – techno Nov 9 '18 at 10:01
• The answer depends on which of the two definitions of DFA you use. Only you can tell. – Yuval Filmus Nov 9 '18 at 15:09