NFA — formal definition, epsilon transitions: Visual walkthrough

We will follow one concrete machine for the language "strings over ${0, 1}$ that end in 1", and feed it the string 101. By the end you will have watched the machine's "cloud of possible positions" breathe in and out.

Step 1 — A state is a bubble, a move is an arrow

WHAT. Before any formula, meet the raw ingredients. A state is just a labelled circle — a place the machine can be. A transition is an arrow from one bubble to another, labelled with the input symbol that triggers it.

WHY. Every symbol in the 5-tuple $N = (Q, Σ, δ, q_{0}, F)$ is a name for something in this picture. We anchor the picture first so the symbols have somewhere to point.

PICTURE. Two bubbles $q_{0}$ and $q_{1}$ . The little stub-arrow with no source points at $q_{0}$ — that marks it as the start state. The double ring around $q_{1}$ marks it as an accepting state (a "you win here" bubble). Arrows carry labels 0 or 1.

Figure — NFA — formal definition, epsilon transitions

Notice $q_{0}$ on symbol 1 has two outgoing arrows: one looping back to $q_{0}$ , one going to $q_{1}$ . That double arrow is the guess "maybe this 1 is the final one, maybe it isn't."

Step 2 — $δ$ is a lookup table that returns a set

WHAT. The arrows of Step 1, written as a table. Each cell answers: "from this state, on this symbol, which bubbles can I land in?"

WHY. We need $δ$ in symbols to plug into the formula. The one thing to burn into memory: each cell holds a set (drawn with braces ${}$ ), possibly empty ( $\emptyset$ ), never a single bare state.

PICTURE. The transition table, colour-coded to the arrows.

Step 3 — The machine's position is a set of bubbles, not one

WHAT. Because of the fork, after some input the machine is not "at a bubble" — it is in a cloud of bubbles at once, all in superposition. We draw the cloud as a set of glowing bubbles.

WHY. This is the mental shift that makes the formula readable. Every glowing bubble is one live guess. The whole run is the story of this cloud growing and shrinking.

PICTURE. The start cloud. Before reading anything, we are at $q_{0}$ — but first we must slide along any free ε-arrows. This machine has no ε-arrows, so we stay put.

Step 4 — Read the first `1`: the cloud splits

WHAT. Apply the induction step for the first time. Current cloud is ${q_{0}}$ ; the next symbol is 1.

WHY. This shows the two halves of the formula: first the union $⋃_{r} δ (r, a)$ (fire every live bubble on the symbol), then ECLOSE (slide for free afterward).

PICTURE. From the single glowing $q_{0}$ , the 1-arrows fan out to $q_{0}$ and $q_{1}$ . Two bubbles now glow.

Step 5 — Read the `0`: one guess dies, one survives

WHAT. Cloud is ${q_{0}, q_{1}}$ ; next symbol 0. Fire both live bubbles.

WHY. This is the step where a branch dies — the crucial illustration that $\emptyset$ prunes without crashing.

PICTURE. From $q_{0}$ the 0-arrow loops back to $q_{0}$ (survives). From $q_{1}$ there is no 0-arrow — that glow goes dark. Cloud shrinks to ${q_{0}}$ .

Step 6 — Read the final `1`, then check for a win

WHAT. Cloud is ${q_{0}}$ ; last symbol 1. Fire it, then test the acceptance rule.

WHY. This closes the trace and shows the existential acceptance test $\hat{δ} (q_{0}, w) \cap F \neq = \emptyset$ in the picture.

PICTURE. The fork fires again from $q_{0}$ : cloud becomes ${q_{0}, q_{1}}$ . We overlay $F = {q_{1}}$ (double ring). The intersection is non-empty — a green checkmark on $q_{1}$ .

Step 7 — The degenerate cases you must also see

WHAT. Three edge scenarios, each drawn so you never meet an unshown situation.

WHY. The contract: cover empty input, a fully-dead cloud, and the role of ε at the start.

PICTURE. Three mini-frames side by side.

The one-picture summary

WHAT. The whole run of 101 as a left-to-right timeline of clouds: ${q_{0}} \to {q_{0}, q_{1}} \to {q_{0}} \to {q_{0}, q_{1}}$ , with the final cloud touching $F$ .

Recall Feynman retelling (say it out loud)

Imagine you are a swarm, not a single walker. You start standing on the start bubble — and instantly you also stand on every bubble you can reach through free doorways (ε-arrows). Now someone reads you a letter. Every copy of you that has a matching arrow steps along it; copies that don't have a matching arrow just vanish. After stepping, you again spread through all free doorways. Repeat for each letter. When the letters run out, you win if even a single copy of you is standing on a double-ringed bubble. That "even a single copy" is the whole soul of nondeterminism — you only need to be lucky once.

Recall Quick self-test

Where is the cloud after reading 1 from 101? ::: ${q_{0}, q_{1}}$ Why did $q_{1}$ vanish after the 0? ::: $δ (q_{1}, 0) = \emptyset$ — dead branch, pruned. What test decides acceptance? ::: final cloud $\cap F \neq = \emptyset$ (there exists a final bubble). Why ECLOSE before the first symbol? ::: it settles whether $ε$ (and free slides) already reach a final state.

Where next: the "cloud of bubbles" you just watched is literally a single state of a DFA — that observation is the whole trick of Subset Construction (NFA to DFA), and it is why NFAs and DFAs accept the same Regular Languages. See also DFA — formal definition, Regular Expressions, and Closure Properties of Regular Languages.