Finite automata — DFA - formal definition (5-tuple), state diagrams: Visual walkthrough

Step 1 — A state is a place to stand

WHAT. Before any letters, before any arrows, we need the raw ingredient: places the machine can be. Draw them as circles. Each circle is one element of the set $Q$ .

WHY. A machine with "no scratch paper" has to encode everything it remembers in a single fact: which circle am I on right now? So the circles are not decoration — collectively they are the machine's entire memory. If two different pasts should lead to the same future behaviour, they may share a circle; if they must be treated differently, they need different circles.

For "ends in 1" the only past fact that matters is the last symbol I read. That splits all histories into exactly two buckets, so we draw two circles:

$Q = {"last was 0, or nothing yet" q_{0}, "last was 1" q_{1}}$

$Q$ — the set of all circles (must be finite; here size $2$ ).
$q_{0}$ — the circle meaning "I have not yet seen a $1$ as the most recent symbol".
$q_{1}$ — the circle meaning "the most recent symbol was a $1$ ".

PICTURE. Two bare circles, no arrows yet — just the vocabulary of places.

Step 2 — Mark WHERE we start and WHICH endings mean "yes"

WHAT. Add two annotations to the circles from Step 1:

a stub arrow from nowhere pointing at $q_{0}$ — this is the start state;
a double ring around $q_{1}$ — this is an accept state.

WHY. A machine needs a place to begin (otherwise "reading a string" has no starting point) and a way to say yes at the end. These are the tuple entries

$q_{0} \in Q and F = {q_{1}} \subseteq Q .$

$q_{0}$ — the start circle. The stub-from-nowhere is the universal picture-code for "put your finger here before reading."
$F$ — the set of glowing circles. "Ends in 1" should say YES exactly when the last symbol was a $1$ , i.e. when we finish on $q_{1}$ ; so $F = {q_{1}}$ . We drew $q_{0}$ not glowing because a string ending in $0$ (or the empty string) must say NO.

PICTURE. Same two circles, now with the start stub on $q_{0}$ and a double ring on $q_{1}$ .

Step 3 — The transition function $δ$ is "one arrow per (circle, letter)"

WHAT. For every circle and every letter of the alphabet $Σ = {0, 1}$ , draw exactly one outgoing arrow saying where that letter sends you. This is the function

$δ : Q \times Σ \to Q .$

$Q \times Σ$ — the input side: every pair (circle, letter). With $2$ circles and $2$ letters that is $2 \times 2 = 4$ pairs.
$\to Q$ — the output side: each pair points to one circle.

WHY "exactly one" and why "for every pair"? The word deterministic means: from where you stand, the next letter leaves you no choice — precisely one arrow to follow. And total means no pair is left out — otherwise the machine could read a letter and have nowhere to go, which is undefined behaviour, not a decision. This is the whole difference from an NFA (which may offer several arrows or none).

The four facts for our machine:

\delta(q_0,0)=q_0 & \text{a }0\text{ keeps "last was 0"} &\quad \delta(q_0,1)=q_1 & \text{a }1\text{ moves to "last was 1"}\\ \delta(q_1,0)=q_0 & \text{a }0\text{ erases the 1} &\quad \delta(q_1,1)=q_1 & \text{a }1\text{ keeps "last was 1"} \end{array}$$ Read each line as *"standing on the left circle, hearing that letter, hop to the right circle."* **PICTURE.** Now the two circles carry all four labelled arrows (self-loops for the "stay" cases). > [!formula] The full 5-tuple we just assembled > $$M=\big(\underbrace{\{q_0,q_1\}}_{Q},\ \underbrace{\{0,1\}}_{\Sigma},\ \underbrace{\delta}_{\text{4 arrows}},\ \underbrace{q_0}_{\text{start}},\ \underbrace{\{q_1\}}_{F}\big)$$ > Every symbol here was *earned* in Steps 1–3: circles, glow, start-stub, arrows. --- ## Step 4 — One letter is one hop (watch the finger move) **WHAT.** We now *run* the machine. Put your finger on $q_0$ (the start). Read the first letter of $w=1011$, which is $1$, and follow the arrow $\delta(q_0,1)=q_1$. Your finger is now on $q_1$. **WHY.** This is the atomic act of computation: **current circle + next letter → new circle**, nothing else. The machine has *forgotten* everything about how it got to $q_0$; all it uses is the arrow leaving the circle its finger is on. That amnesia is exactly what "finite memory, no scratch paper" means — and it is *why* $\delta$ takes only a state and a symbol, never the whole history. $$q_0 \xrightarrow{\ 1\ } q_1$$ - left ($q_0$) — where the finger was; - label ($1$) — the letter just consumed; - right ($q_1$) — where the finger lands, dictated by $\delta$. **PICTURE.** The board with the finger's single hop highlighted, and the remaining unread letters $\texttt{011}$ waiting. --- ## Step 5 — Chaining hops = the extended function $\hat\delta$ **WHAT.** A string is just letters in a row, so *reading a string* is *hopping repeatedly*. Continue $1011$ from where Step 4 left off ($q_1$): $$q_0 \xrightarrow{\,1\,} q_1 \xrightarrow{\,0\,} q_0 \xrightarrow{\,1\,} q_1 \xrightarrow{\,1\,} q_1$$ **WHY we give this a name.** The one-letter $\delta$ cannot *directly* eat a four-letter string. We package "do the hops in order" into a new function $$\hat\delta : Q \times \Sigma^{*} \to Q,$$ - $\Sigma^{*}$ — the set of **all strings** over $\{0,1\}$ (any length, including the empty one); - $\hat\delta(q,w)$ — the circle you end on if you start on $q$ and read the *whole* string $w$. Its definition just says "hop all but the last letter, then take one more $\delta$-step": $$\hat\delta(q,\varepsilon)=q \qquad\qquad \hat\delta(q,xa)=\delta\big(\hat\delta(q,x),\,a\big)$$ - $\varepsilon$ — the empty string; reading nothing leaves the finger put (base case); - $xa$ — a string $x$ followed by one final letter $a$; process $x$ first (the inner $\hat\delta$), *then* the last hop $\delta(\dots,a)$. The full run lands on $q_1$, so $\hat\delta(q_0,1011)=q_1$. **PICTURE.** The whole path $q_0\!\to\!q_1\!\to\!q_0\!\to\!q_1\!\to\!q_1$ drawn as a trail of numbered footprints across the board. --- ## Step 6 — The verdict: is the final circle glowing? **WHAT.** Reading ended on $q_1$. Look down: $q_1$ has the double ring, i.e. $q_1\in F$. So the machine shouts **YES** — $1011$ is accepted. **WHY this is the definition of "accept".** All the machinery collapses to one final check: $$w \text{ is accepted } \iff \hat\delta(q_0,w)\in F.$$ - $\hat\delta(q_0,w)$ — the circle the finger rests on after the whole string; - $\in F$ — "is it one of the glowing circles?" — the yes/no readout. And the set of *all* strings that pass this test is the **language of the machine**: $$L(M)=\{\,w\in\Sigma^{*} : \hat\delta(q_0,w)\in F\,\}=\{\,w : w\text{ ends in }1\,\}.$$ A language obtainable this way from *some* DFA is called **regular** — the exact class handled by [[Regular expressions|regular expressions]] and [[Lexical analysis / tokenizers|tokenizers]]. **PICTURE.** The end of the trail on $q_1$ with a big glowing "ACCEPT ✓" annotation. --- ## Step 7 — Edge case A: the empty string $\varepsilon$ **WHAT.** Feed the machine *nothing*. By the base case $\hat\delta(q_0,\varepsilon)=q_0$: the finger never moves. Since $q_0\notin F$, the empty string is **rejected**. **WHY it matters.** $\varepsilon$ is the sneakiest input — there are no hops to watch, so people forget to test it. The rule is beautifully simple: $$\varepsilon \text{ accepted } \iff q_0 \in F.$$ Here "ends in 1" should reject the empty string (it has no last symbol that is a $1$), and indeed $q_0\notin F$. The machine is correct on the degenerate case *for free*. **PICTURE.** The board with the finger sitting on $q_0$, no arrows used, a grey "REJECT ✗" tag. --- ## Step 8 — Edge case B: a missing arrow hides a dead state **WHAT.** Suppose someone hands you a diagram for "*strings that start with $1$*" and simply **omits** the arrow for reading $0$ at the start — as if $\delta(\text{start},0)$ were undefined. A real DFA is not allowed to have a hole. The hole *secretly* means: send that input to a **dead (trap) state** $q_{d}$ that loops to itself on every letter and never glows. **WHY.** $\delta$ must be **total** (Step 3). "Undefined" is not a valid destination; the honest completion is a circle you can never escape and that always says NO. Once the finger falls into $q_{d}$, every remaining letter keeps it there: $$\delta(q_{d},0)=q_{d}\qquad \delta(q_{d},1)=q_{d}\qquad q_{d}\notin F.$$ - $q_{d}$ — the newly revealed trap circle; - the two self-loops — "no letter can rescue you"; - $\notin F$ — "and you can never say YES from here." So a "reject" ending is a first-class outcome, not a crash — which is why *every* string, good or bad, gets a definite verdict. **PICTURE.** A tiny start-fragment with the previously-missing $0$-arrow drawn in red into a shaded trap circle $q_{d}$ that self-loops on $0$ and $1$. --- ## The one-picture summary Every idea on this page in a single frame: the two circles ($Q$), the start stub ($q_0$), the double ring ($F$), the four arrows ($\delta$), the footprint trail of $\hat\delta(q_0,1011)$, and the final glow (accept). Below it sits the tiny trap circle from Step 8 to remind you that *reject is a real state too*. > [!recall]- Feynman retelling — the whole walkthrough in plain words > I drew a few circles; each circle is the *only* thing my machine remembers. I put a little arrow-from-nowhere on one to say "start here," and I drew a double ring on the circles that mean "YES." Then for every circle and every possible letter I drew exactly one arrow — no choices, no missing arrows — so the machine always knows its one next move. To read a word I just put my finger on the start and hop along the arrows, one hop per letter, forgetting the past completely each time. That "hop for every letter in order" is what the fancy hat-delta $\hat\delta$ means, and its base case is "reading nothing keeps my finger where it is." When the letters run out I look down: standing on a glowing double-ring circle means shout YES, otherwise NO. The empty word is decided *before* any hop — just check if the start circle glows. And if a diagram looks like it's missing an arrow, that arrow secretly leads to a hopeless trap circle that loops forever and never glows, so *every* word still gets a clean yes-or-no. > [!recall]- Self-check > What does $\hat\delta(q_0,1011)$ equal for the "ends in 1" machine, and is it accepted? ::: $q_1$; and $q_1\in F$, so **accepted**. > Is $\varepsilon$ accepted by the "ends in 1" machine? ::: No — $\hat\delta(q_0,\varepsilon)=q_0\notin F$. > What does a missing arrow in a DFA diagram really stand for? ::: A transition into a dead/trap state that self-loops on every symbol and is non-accepting. > Why must every (circle, letter) pair have exactly one arrow? ::: Because $\delta$ is a **total, single-valued** function — that is what "deterministic" means; multiple/no arrows would make it an [[NFA — nondeterministic finite automata|NFA]]. --- Related: [[Subset construction (NFA → DFA)]] · [[DFA minimization (Myhill–Nerode)]] · [[Regular languages and the Pumping Lemma]]

Step 1 — A state is a place to stand

Step 2 — Mark WHERE we start and WHICH endings mean "yes"

Step 3 — The transition function δ is "one arrow per (circle, letter)"

Step 3 — The transition function $δ$ is "one arrow per (circle, letter)"