# Every DFA accepting a finite language must contain a dead state?

I came a across a question where there were some statements made on Finite Automata, DFA and their states.

One such statements in the question was that a "Every DFA accepting a finite language must contain a dead state"

And the answer stated the statement to be true, and showed some DFA where there was a dead state following the accepting/final state.

Yes, dead states after the final state is possible but what about languages like $$(a+b)^*$$ ? It is a finite language and there is no need for a dead state in it's DFA:

There is no dead state in this DFA. Am I making a mistake somewhere?

Yes you are making a mistake. There is an important condition here, which is finite.

The language $$(a+b)^*$$ is not finite. For $$L$$ any language, $$L^*$$ is finite if and only if $$L = \emptyset$$ or $$L = \{\varepsilon\}$$.

• Oh, yeah thanks for pointing it out. That's a silly misconception on my part
– h4kr
Jan 26 at 15:31

"Every DFA accepting a finite language must contain a dead state"

This depends on the definition. If dead state is the same as what some call a garbage state (not accepting, for all letters a loop back to the state) then this statement is not true. See the automaton below, which accepts only the empty string. This example can be generalized to other finite languages.

Alternatively, dead state might mean at state from which no accepting state is reachable. In that case the above statement is true.