Deterministic Finite Automata (DFA)

the DFA five-tuple

When we want to be precise rather than draw a picture, a DFA is written as a five-tuple, a list of exactly five ingredients packaged together: M = (Q, Σ, δ, q0, F). Think of it as the full recipe card for the machine — once you have these five things, the machine is completely specified and there is nothing left to guess.

Reading the five ingredients in order: Q is the finite set of states (the circles in the diagram). Σ (Sigma) is the input alphabet — the finite set of symbols the machine is allowed to read. δ (delta) is the transition function: it takes a state and a symbol and returns exactly one next state, written δ(q, a) = p, meaning 'from state q, reading symbol a, go to state p'. q0 (an element of Q) is the start state, where every run begins. F (a subset of Q) is the set of accept states, the ones whose double circle says 'if you finish here, say yes'. That is the entire machine.

Every other notion about DFAs is defined on top of this tuple: a run is the sequence of states produced by repeatedly applying δ; the extended transition function feeds a whole string through δ; acceptance asks whether the ending state lies in F; and the language recognised by M is the set of all strings it accepts. Getting the tuple right is the discipline that turns a hand-wavy diagram into something you can prove things about.

The 'ends in 1' DFA as a tuple: Q = {A, B}, Σ = {0, 1}, q0 = A, F = {B}, and δ given by δ(A,0)=A, δ(A,1)=B, δ(B,0)=A, δ(B,1)=B. Five lines fully specify the machine; no diagram required.

(Q, Σ, δ, q0, F): states, alphabet, transitions, start, accepts — nothing more is needed.

Order and roles are fixed by convention: q0 is a single state (not a set), while F is a set that may be empty (then the DFA accepts nothing) or all of Q (then it accepts everything over Σ*).

Also called
DFA formal definition(Q, Σ, δ, q0, F)DFA 形式定義五元組