Deterministic Finite Automata (DFA)

a state diagram

A state diagram is the picture of a finite automaton — the friendly, visual way to see the machine. Each state is a circle, each transition is a labelled arrow from one circle to another, the start state has a stray arrow pointing into it from nothing, and each accept state is drawn as a double circle. You can read a whole machine off the page at a glance.

To run a string by hand on a diagram, put your finger on the start circle. For each input symbol, follow the arrow leaving your current circle whose label is that symbol — there is exactly one such arrow in a DFA, since δ is deterministic and total. When the input is finished, look at the circle your finger rests on: if it is a double circle, accept; otherwise reject. Arrows that return to the same circle (self-loops) are common and just mean 'stay here on this symbol'.

The diagram and the formal five-tuple are two views of the same object: every arrow labelled a from circle q to circle p is exactly the equation δ(q, a) = p, the start arrow names q0, and the double circles name F. Diagrams are wonderful for getting intuition and for design, but for proofs and for feeding a machine to a computer the tuple or the transition table is what you reach for.

The 'ends in 1' DFA drawn: a start arrow into circle A; from A a self-loop labelled 0 and an arrow labelled 1 to circle B (double circle); from B a self-loop labelled 1 and an arrow labelled 0 back to A. Tracing 101: A -(1)-> B -(0)-> A -(1)-> B, finger ends on the double circle B, so accept.

Circles = states, arrows = δ, double circle = accept, stray inbound arrow = start.

In a correct DFA diagram, every circle must have exactly one outgoing arrow per alphabet symbol (totality and determinism). A diagram missing an arrow is either incomplete or secretly an NFA.

Also called
transition diagramstate-transition diagram狀態轉移圖狀態圖