Foundations — NFA — formal definition, epsilon transitions

Before you can read a single line of the parent note, you need a small toolbox. This page builds each tool from nothing — plain words first, then the picture, then why the NFA needs it. Nothing is used before it is defined.

1. A set — the bag that holds things

The picture: imagine a real cloth bag with three labelled marbles inside. Shaking the bag changes nothing — $\{q_0,q_1\}$ and $\{q_1,q_0\}$ are the same set.

Why the topic needs it. The whole point of an NFA is that after reading a symbol you may be in several states. "Several states" is exactly a set of states. Without the idea of a bag we could not even say "the machine is in $\{q_0,q_1\}$ right now."

2. Subset and $\subseteq$ — a smaller bag inside a bigger one

The picture: a big circle $B$; a smaller circle $A$ drawn entirely inside it. Nothing of $A$ pokes out.

Why the topic needs it. The parent writes $F\subseteq Q$ — the accepting states $F$ are a smaller bag sitting inside the bag of all states $Q$. Some states win, some don't; the winners are a subset.

3. The power set $\mathcal{P}(Q)$ — the bag of ALL possible bags

This is the trickiest symbol in the parent note, so we build it slowly.

The picture: if $Q=\{q_0,q_1\}$, lay out every sub-bag you can make: $\mathcal{P}(Q)=\{\varnothing ,\{q_0\},\{q_1\},\{q_0,q_1\}\}$ That is $4$ bags. In general a set of $n$ items has $2^n$ subsets, because each item is independently either in or out.

Why the topic needs it. The parent note's transition rule (a rule we build fully in §4) will hand back a set of states. To describe "returns a set of states — one, many, or none" precisely, we need the collection of all possible such sets. That collection is exactly $\mathcal{P}(Q)$, and being able to return any member of it is what will give the NFA its multiple/zero targets.

4. A function, its arrow $\to$, and the NFA transition rule $\delta$

The picture: a little vending machine. You press a button (input); one item drops out (output). Same button always gives the same item.

Why the topic needs it. $\delta$ is the heart of the machine — the rule that tells it where it may go. Its arrow's left side (input) and right side (output) are the definition of the machine's behaviour.

5. The Cartesian product $\times$ — pairing two bags

The picture: a grid. List $A$ down the left, $B$ across the top; every cell is one pair. If $A$ has 3 items and $B$ has 2, the grid has $3\times 2=6$ cells.

Why the topic needs it. The input to $\delta$ is a pair (which state am I in, which symbol did I just read). You always need both to decide the next move, so the input must be a pair, and pairs come from a Cartesian product. The exact bags being paired are named in §6–§8.

6. The alphabet $\Sigma$ and strings ${\Sigma }^{\ast }$

The picture: $\Sigma$ is your box of alphabet tiles; a string $w$ is a row of tiles laid left-to-right; ${\Sigma }^{\ast }$ is the infinite catalogue of every row you could ever lay, from length 0 upward.

Why the topic needs it. The machine's job is to answer "is this string $w$ in the language?" for strings drawn from ${\Sigma }^{\ast }$. The set of all strings the machine accepts is a subset of that catalogue (we name that set in §10).

7. Epsilon $\epsilon$ — the empty string

The picture: a completely blank row on the table. There is a row there (it exists), it just holds nothing.

Why the topic needs it. ε-transitions — letting the machine change state without reading input — are one of the two superpowers of an NFA. You cannot describe them without a name for "no symbol."

8. Union $\cup$ and intersection $\cap$ — combining bags

The picture: two overlapping circles (a Venn diagram). Union shades both circles; intersection shades only the overlap.

Why the topic needs it.

• $\Sigma \cup \{\epsilon \}$ uses union to bolt the free-move label onto the real symbols — this is exactly the input-symbol side of $\delta$.
• Intersection powers the acceptance test we meet in §9: do any of the states I ended in overlap with the winning states? If the overlap is non-empty, the machine accepts.

9. Running a whole string: $\hat{\delta }$, then "there exists" $\exists$

$\delta$ (from §4) answers only for one symbol. To run an entire string $w$ we need a companion rule that applies $\delta$ symbol after symbol.

The picture: many trails leaving a trailhead. If even one trail reaches the summit, you "reached the summit." The failed trails don't count against you.

Why the topic needs it. This is the heartbeat of nondeterminism. The acceptance test says: the final cloud $\hat{\delta }(q_0,w)$ must share at least one state with the winning set $F$ — written $\hat{\delta }(q_0,w)\cap F\ne \varnothing$. This literally means "there exists a surviving path that ends on a winner." Contrast this with the wrong idea $\subseteq F$ ("all paths win"), which the parent flags as a classic mistake.

10. Naming the whole machine: $N$ and its language $L(N)$

The picture: $N$ is the whole vending machine sitting on the table; $L(N)$ is the list of every input string that makes its "accept" light turn on.

Now every symbol in the parent's central definition is earned: $\delta :\underset{\text{§1 set}}{\underbrace{Q}}\times \underset{\text{§6 }\Sigma ,\text{§7 }\epsilon ,\text{§8 }\cup }{\underbrace{(\Sigma \cup \{\epsilon \})}}⟶\underset{\text{§3 power set}}{\underbrace{\mathcal{P}(Q)}}$ Read it aloud: "$\delta$ takes a pair (§5) — a state and a (symbol-or-free-move) — and returns a set of states." That single line is nondeterminism.

Every arrow above feeds the parent topic NFA formal definition. These same foundations also power DFA — formal definition, Subset Construction (NFA to DFA), Regular Languages, Regular Expressions, and Closure Properties of Regular Languages.

Equipment checklist

Cover the right side and test yourself — if any line stumps you, reread its section.