Introduction

Alright, let’s pivot to finite automata! The Emptiness Problem for Deterministic Finite Automata (DFAs) asks: given a DFA $M$, does it accept no strings at all? Good news: this one is super easy and efficiently decidable.

Formal Setup

A DFA is a 5-tuple

$$ M = (Q, Σ, δ, q_0, F) $$

where

  • $Q$ is a finite set of states,
  • $Σ$ is the input alphabet,
  • $δ: Q \times Σ \to Q$ is the transition function,
  • $q_0 \in Q$ is the start state,
  • $F \subseteq Q$ is the set of accepting states.

Its language is

$$ L(M) = {,w \in Σ^* \mid δ^*(q_0, w) \in F}. $$

The Emptiness Problem asks whether $L(M) = \emptyset$.

Example DFAs

# DFA D1:
# Q = {q0, q1}, Σ = {0,1}, q0 start, F = {q1}
# δ(q0,0)=q0, δ(q0,1)=q1
# δ(q1,0)=q1, δ(q1,1)=q1
# This accepts any string containing at least one '1', so L(D1) ≠ ∅.

# DFA D2:
# Q = {p0, p1}, Σ = {a,b}, p0 start, F = {p1}
# δ(p0,a)=p0, δ(p0,b)=p0
# δ(p1,a)=p1, δ(p1,b)=p1
# Note: no transition ever reaches p1 from p0, so L(D2) = ∅.

  • Question: Does $D1$ accept any string? Answer: Yes, e.g., “1”.

  • Question: Does $D2$ accept any string? Answer: No, state $p1$ is unreachable from the start.

Algorithm (Reachability Check)

  1. Compute the set of states reachable from $q_0$ via a simple BFS or DFS on the transition graph.
  2. Check: if any accepting state in $F$ is in the reachable set, then $L(M) ≠ ∅$; otherwise $L(M) = ∅$.

This runs in $O(|Q| + |δ|)$ time, which is linear in the size of the DFA.

Why It Matters

  • Quick Verification: Useful in compiler construction and model checking to verify that certain patterns or tokens can actually occur.
  • Optimization: You can prune unreachable or useless parts of your automaton.

Wrap-Up

Emptiness for DFAs is trivial compared to what we’ve seen before, just check reachability! Next up: the Equivalence Problem for DFAs, which is also decidable and surprisingly elegant.