Course contentsShow
← Computer Science
Lesson 1780 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

DFA Computation and Acceptance

How a DFA processes input strings symbol-by-symbol and determines acceptance based on ending in an accept state.

DFA Computation and Acceptance

What You'll Learn

You'll learn exactly how a DFA reads an input string character by character and decides whether to accept or reject it.

How DFAs Process Input

A DFA (Deterministic Finite Automaton) is like a machine that reads input one symbol at a time, following a strict set of rules. Think of it as a board game where you move from space to space based on dice rolls—except here, each input symbol tells you exactly which state to move to next.

The Computation Process

  1. Start in the initial state - Every DFA begins at a designated start state
  2. Read the first symbol - Look at the leftmost character of your input string
  3. Follow the transition - Move to the next state according to the transition function for that symbol
  4. Repeat - Continue reading symbols left-to-right, transitioning between states
  5. Check final position - When the string is exhausted, see where you ended up

Acceptance Criteria

A DFA accepts a string if and only if:

  • After processing all input symbols, the DFA lands in an accept state (also called a final state)

A DFA rejects a string if:

  • After processing all symbols, it ends in a non-accept state

Example Walkthrough

Suppose your DFA has states q0 (start), q1, and q2 (accept). On input "ab":

  • Start at q0
  • Read 'a', transition to q1
  • Read 'b', transition to q2
  • No more input; currently in q2 (an accept state) → ACCEPT

Key Takeaway: A DFA accepts a string by following transitions symbol-by-symbol and ending in an accept state; the computation is deterministic and always produces a yes/no answer.