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

The Acceptance Problem for DFAs

Prove that determining if a DFA accepts a string is decidable by constructing a deciding TM.

The Acceptance Problem for DFAs

You'll learn: How to prove that checking whether a DFA accepts a given string is a decidable problem by constructing a Turing Machine that always halts with the correct answer.

What Is the Acceptance Problem?

The acceptance problem for DFAs asks: "Given a DFA M and a string w, does M accept w?" This seems straightforward—just run the DFA on the string—but to prove it's decidable, we need to show a Turing Machine can solve it and always halt with a yes/no answer.

Why This Matters

Decidability is about guaranteeing answers. Some problems might loop forever without answering. For DFAs, we can prove this never happens: we always get a definite accept or reject decision.

Constructing the Deciding Turing Machine

Here's how we build a TM T that decides the acceptance problem:

  1. Input: Encode both the DFA M (its states, transitions, start state, accept states) and the string w on the tape
  2. Simulate: Run M on w step-by-step, tracking the current state as you read each symbol
  3. Check: After processing all of w, check if you ended in an accept state
  4. Halt: If yes, enter the TM's accept state; otherwise, enter the reject state

This TM always halts because DFAs have finite strings and must transition on every symbol—no infinite loops possible. Since we always get an answer, the problem is decidable.

The Bigger Picture

This proof is foundational. It establishes that at least some problems about computation are decidable, giving us a baseline before exploring undecidable problems.

Key Takeaway: The acceptance problem for DFAs is decidable because we can construct a Turing Machine that simulates the DFA, always halts, and correctly reports whether the string is accepted.