the DFA emptiness problem

Now a question not about one string but about the whole language a DFA recognizes: does this DFA accept ANY string at all, or is its language empty? As a language, E_DFA = {B : B is a DFA and the language of B is the empty set ∅}. You might worry this requires checking infinitely many strings, but it does not — there is a clever way to settle it by looking only at the machine's wiring.

The trick is to forget the strings and look at the DFA as a graph of states with labelled arrows. A DFA accepts some string if and only if there is a path of transitions from the start state to at least one accept state. (A path spelling out the symbols along the way IS an accepted string, and any accepted string traces such a path.) So the question becomes pure reachability: starting from the start state, repeatedly mark every state reachable in one transition from an already-marked state, until no new states get marked. This marking process stops because there are only finitely many states. When it stops, check whether any accept state got marked. If none did, the language is empty (accept B into E_DFA); if some did, the language is non-empty (reject).

Hence E_DFA is DECIDABLE. This is a small but pivotal result. It shows that even a question quantifying over infinitely many possible inputs can be decided by a finite graph search, because a finite automaton has only finitely many states to explore. Emptiness testing is also a workhorse used to build other decision procedures — for instance, to decide whether two DFAs are equivalent you reduce to an emptiness test on a cleverly combined machine.