Deterministic Finite Automata (DFA)

Deterministic Finite Automata (DFA)

A DFA is a finite automaton where for every state and every input symbol, there is exactly one transition. "Deterministic" means the machine's next state is completely determined by its current state and the input symbol — no guessing, no ambiguity.

A DFA is formally defined as a 5-tuple (Q, Σ, δ, q0, F) where δ: Q × Σ → Q is a total function — it must produce a next state for every state-symbol pair.

State Diagrams

DFAs are typically visualized as directed graphs. Circles represent states, and directed edges represent transitions. The start state has an incoming arrow with no source. Accept states are marked with double circles.

Example: DFA accepting strings ending in "01"

    ┌───0───┐    ┌───1───┐
    │       ▼    │       ▼
  ┌───┐       ┌───┐       ┌═══┐
  │q0 │──0──▶ │q0 │──1──▶ │q1 │
  └───┘       └───┘       └═══┘
   ▲            ▲           │
   │     0      │     0     │
   └────────────┴───────────┘
   │            │     1     │
   └────────────┴───────────┘

Start: q0
Accept: {q1}

δ(q0, 0) = q0
δ(q0, 1) = q1
δ(q1, 0) = q0
δ(q1, 1) = q1

Trace Execution

Let's trace "101" through the DFA above. Start at q0. Read 1 → move to q1. Read 0 → move to q0. Read 1 → move to q1. End in q1 (accept). So "101" is accepted.

Now trace "100". Start at q0. Read 1 → move to q1. Read 0 → move to q0. Read 0 → stay at q0. End in q0 (reject). So "100" is not accepted — it doesn't end in "01".

Key Properties

A DFA has no epsilon transitions. From any state, reading any symbol from the alphabet leads to exactly one state. This makes DFAs easy to simulate — you just follow the transitions. There's no branching, no backtracking, and no ambiguity.

Every regular language has a DFA that accepts it. The number of states in the minimal DFA for a language is unique — this is the Myhill-Nerode theorem.