0
$\begingroup$

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:

(a+b)* DFA

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

$\endgroup$

2 Answers 2

2
$\begingroup$

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\}$.

$\endgroup$
1
  • $\begingroup$ Oh, yeah thanks for pointing it out. That's a silly misconception on my part $\endgroup$
    – h4kr
    Jan 26, 2023 at 15:31
0
$\begingroup$

"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.

automaton accepting only the empty string without dead state

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.