Formal definition of DFA

A deterministic finite automaton (DFA) is a 5-tuple

M = (Q, Σ, δ, q₀, F)

where

• Q is a finite, non-empty set of states,
• Σ is a finite input alphabet,
• δ : Q × Σ → Q is the transition function (exactly one next state for each state and symbol),
• q₀ ∈ Q is the start state,
• F ⊆ Q is the set of final (accepting) states.

Extended transition function δ* : Q × Σ* → Q:

• δ*(q, ε) = q
• δ*(q, wa) = δ(δ*(q, w), a) for w ∈ Σ*, a ∈ Σ

Language accepted: L(M) = { w ∈ Σ* : δ*(q₀, w) ∈ F }. A language is regular iff some DFA accepts it.

Example

DFA over {0, 1} accepting strings that end in 1: M = ({q0, q1}, {0,1}, δ, q0, {q1}).

         0                    1
       ┌───┐                ┌───┐
       │   ▼        1       │   ▼
 ──►   (q0) ─────────────► ((q1))
         ▲                    │
         └──────── 0 ─────────┘

(→ marks the start state, * a final state.) For input 011: q0 →0 q0 →1 q1 →1 q1, which is final, so 011 is accepted.