# 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. Nov 9, 2018 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. Nov 9, 2018 at 11:19
• @rus9384 okay...thanks . Is the elimination of the dead state mentioned in this problem correct . ibb.co/iav4QA Nov 9, 2018 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. Nov 9, 2018 at 17:21
• @rus9384 why? 1 and 5 can be combined into a single state as they have identical transitions . Nov 13, 2018 at 9:59

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 Nov 9, 2018 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.
– SSM
Nov 10, 2018 at 14:11
• hmm strange its from GATE 2019 book by Pearson.. Nov 13, 2018 at 10:00
• Please see the update... is this a correct solution to the question in the comment. Nov 13, 2018 at 10:06
• @techno it seems correct to me, state 4 is the trap state and any input thereafter will be trapped in it.
– SSM
Nov 14, 2018 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... Nov 9, 2018 at 10:01
• The answer depends on which of the two definitions of DFA you use. Only you can tell. Nov 9, 2018 at 15:09