Course contentsShow
← Computer Science
Lesson 1872 of 2,87242. Turing Machines and ComputabilityFree lesson

The Emptiness Problem for DFAs

Show that testing whether a DFA accepts any string is decidable using reachability analysis.

The Emptiness Problem for DFAs

You'll learn: How to algorithmically determine whether a DFA accepts at least one string—and why this problem is decidable.

The Core Question

Given a DFA, does it accept any string at all, or does it reject everything? This is called the emptiness problem: deciding whether the language of a DFA is empty or not.

Think of it like checking if there's any path from your front door to your kitchen. You don't need to explore every possible route through your house—you just need to know if the kitchen is reachable at all.

The Reachability Solution

Here's the elegant insight: A DFA accepts at least one string if and only if at least one accepting state is reachable from the start state.

The algorithm is simple:

  1. Start at the initial state
  2. Mark it as "reachable"
  3. Repeatedly mark any state reachable via one transition from an already-marked state
  4. Continue until no new states can be marked
  5. Check if any accepting state got marked

If an accepting state is reachable, the DFA accepts the string corresponding to the path from start to that state. If no accepting state is reachable, the DFA's language is empty.

Why This Works

This is just a graph search (like breadth-first or depth-first search) on the DFA's state diagram. Since DFAs have finitely many states, this search always terminates. We get a yes/no answer in finite time, which means the problem is decidable.

Key Takeaway: The emptiness problem for DFAs is decidable because we can use reachability analysis to check if any accepting state is reachable from the start state in finite time.